Token Execution Strategies for Distributed Algorithms: Simulation Studies.

Abstract

Six variations of the token execution strategy of a distributed algorithm are described, applied to an algorithm for computing the minimum-weight spanning tree simulated on three network topologies, and compared with the chaotic execution strategy. In a chaotic execution, a processor may transmit a message M as soon as it generates M. In a token execution, a processor may transmit a message only when it holds a unique token. The token execution limits the number of messages in transit at the time. Execution with one token allows the user to observe the response to each message sequentially; execution with a fixed number of tokens provides a congestion control strategy. The best combination of variations of the token execution strategy uses 5.6% to 15.8% more messages and 0% to 12.3% more execution time than the chaotic execution, depending on network topology.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jul 01, 1987
Accession Number
ADA184792

Entities

People

  • Mark J. Lloyd

Organizations

  • University of Illinois Urbana–Champaign

Tags

Communities of Interest

  • Materials and Manufacturing Processes

DTIC Thesaurus Topics

  • Algorithms
  • Case Studies
  • Classification
  • Computational Science
  • Computer Communications
  • Computer Networks
  • Computer Science
  • Computers
  • Engineering
  • Illinois
  • Mesh Networks
  • Network Topology
  • Security
  • Simulations
  • Simulators
  • Topology
  • Universities

Fields of Study

  • Computer science
  • Engineering

Readers

  • Computer Networking
  • Joint Military Operations and Doctrine.
  • Operations Research