loading...
Developing and Refining an Adaptive Token-Passing Strategy
Mesa, AZ April 16-April 19
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/ICDSC.2001.91899021st IEEE International Conference on ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Burkhard Englert, University of California at Los Angeles
Larry Rudolph, Massachusetts Institute of Technology
Alex Shvartsman, University of Connecticut
Abstract: Token rotation algorithms play an important role in distributed computing, to support such activities as mutual exclusion, round-robin scheduling, group membership and group communication protocols. Ring-based protocols maximize throughput in busy systems, but can incur a linear, in the number of processors, delay when a processor needs to obtain a token to perform an operation. This paper synthesizes these two algorithmic techniques thereby improving performance (responsiveness) of logical ring protocols. The parameterized technique preserves the safety properties of ring protocols and maintains high throughput in busy systems, while reducing the delay in lightly loaded systems from a linear to the logarithmic function in the number of processors. The algorithmic development is done using term rewriting systems where our parameterized protocol is developed in a series of safety-preserving refinements of a basic specification.
Citation:
Burkhard Englert, Larry Rudolph, Alex Shvartsman, "Developing and Refining an Adaptive Token-Passing Strategy," icdcs, pp.0597, 21st IEEE International Conference on Distributed Computing Systems (ICDCS'01), 2001
Usage of this product signifies your acceptance of the Terms of Use.