Distributed Algorithms: 5th International Workshop, WDAG ’91 Delphi, Greece, October 7–9, 1991 Proceedings

Uri Abraham, Shai Ben-David, Shlomo Moran (auth.), Sam Toueg, Paul G. Spirakis, Lefteris Kirousis (eds.)3540552367, 9783540552369

This volume contains the proceedings of the fifth International Workshop on Distributed Algorithms (WDAG ’91) held in Delphi, Greece, in October 1991. The workshop provided a forum for researchers and others interested in distributed algorithms, communication networks, and decentralized systems. The aim was to present recent research results, explore directions for future research, and identify common fundamental techniques that serve as building blocks in many distributed algorithms. The volume contains 23 papers selected by the Program Committee from about fifty extended abstracts on the basis of perceived originality and quality and on thematic appropriateness and topical balance. The workshop was organizedby the Computer Technology Institute of Patras University, Greece.

---

Table of contents :
On the limitation of the global time assumption in distributed systems….Pages 1-8
Causal memory….Pages 9-30
More on the power of random walks: Uniform self-stabilizing randomized algorithms….Pages 31-51
Pseudo read-modify-write operations: Bounded wait-free implementations….Pages 52-70
Maintaining digital clocks in step….Pages 71-79
Implementing FIFO queues and stacks….Pages 80-94
Optimal amortized distributed consensus….Pages 95-107
Optimally simulating crash failures in a byzantine environment….Pages 108-128
Efficient distributed consensus with n=(3 + ɛ)t processors….Pages 129-142
Randomized consensus in expected O(n 2 log n ) operations….Pages 143-150
Using adaptive timeouts to achieve at-most-once message delivery….Pages 151-166
Uniform dynamic self-stabilizing leader election….Pages 167-180
The quickest path problem in distributed computing systems….Pages 181-192
The communication complexity of the two list problem….Pages 193-199
Distributed algorithms for updating shortest paths….Pages 200-211
Minimal shared information for concurrent reading and writing….Pages 212-228
Reading many variables in one atomic operation solutions with linear or sublinear complexity….Pages 229-241
Analysis of distributed algorithms based on recurrence relations….Pages 242-253
Detection of global state predicates….Pages 254-272
Using consistent subcuts for detecting stable properties….Pages 273-288
Atomic m -register operations….Pages 289-294
A robust distributed mutual exclusion algorithm….Pages 295-308
Message delaying synchronizers….Pages 309-318