Distributed Algorithms: 2nd International Workshop Amsterdam, The Netherlands, July 8–10, 1987 Proceedings

Karl Erik Johansen, Ulla Lundin Jørgensen, Svend Hauge Nielsen (auth.), J. van Leeuwen (eds.)3540193669, 9783540193661

This volume presents the proceedings of the 2nd International Workshop on Distributed Algorithms, held July 8-10, 1987, in Amsterdam, The Netherlands. It contains 29 papers on new developments in the area of the design and analysis of distributed algorithms. The topics covered include, e.g. algorithms for distributed consensus and agreement in networks, connection management and topology update schemes, election and termination detection protocols, and other issues in distributed network control.

---

Table of contents :
A distributed spanning tree algorithm….Pages 1-12
Directed network protocols….Pages 13-29
Fault tolerant queries in computer networks….Pages 30-40
General and efficient decentralized consensus protocols….Pages 41-56
A framework for agreement….Pages 57-75
Byzantine firing squad using a faulty external source….Pages 76-83
An improved multiple identification algorithm for synchronous broadcasting networks….Pages 84-91
Distributed algorithms for tree pattern matching….Pages 92-107
On the packet complexity of distributed selection….Pages 108-115
Load balancing in a network of transputers….Pages 116-126
Experience with a new distributed termination detection algorithm….Pages 127-143
A distributed deadlock avoidance technique….Pages 144-154
How to detect a failure and regenerate the token in the Log(n) distributed algorithm for mutual exclusion….Pages 155-166
Verification of connection-management protocols….Pages 167-186
Generalized scheme for topology-update in dynamic networks….Pages 187-196
Local fail-safe network reset procedure….Pages 197-211
Synchronizing asynchronous bounded delay networks….Pages 212-218
A modular proof of correctness for a network synchronizer….Pages 219-256
On the use of synchronizers for asynchronous communication networks….Pages 257-277
Atomic multireader register….Pages 278-296
An optimistic resiliency control scheme for distributed database systems….Pages 297-309
A failsafe scheme for replicated information….Pages 310-323
Randomized function evaluation on a ring….Pages 324-331
A distributed ring orientation algorithm….Pages 332-336
Constructing efficient election algorithms from efficient traversal algorithms….Pages 337-344
Optimal resilient ring election algorithms….Pages 345-354
Fault-tolerant distributed algorithm for election in complete networks….Pages 355-373
Lower bounds for synchronous networks and the advantage of local information….Pages 374-387
On the existence of generic broadcast algorithms in networks of Communicating Sequential Processes….Pages 388-407
Stepwise removal of virtual channels in distributed algorithms….Pages 408-428