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