Accession Number : ADA184792

Title :   Token Execution Strategies for Distributed Algorithms: Simulation Studies.

Descriptive Note : Master's thesis,

Corporate Author : ILLINOIS UNIV AT URBANA COORDINATED SCIENCE LAB

Personal Author(s) : Lloyd,Mark J

PDF Url : ADA184792

Report Date : Jul 1987

Pagination or Media Count : 49

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.

Descriptors :   *DISTRIBUTED DATA PROCESSING, *ALGORITHMS, *ASYNCHRONOUS COMPUTERS, TREES, TABLES(DATA), COMPUTERIZED SIMULATION, MESSAGE PROCESSING, TOPOLOGY, NETWORKS, THESES

Subject Categories : Computer Systems

Distribution Statement : APPROVED FOR PUBLIC RELEASE