Distributed Algorithms

1. Front Matter

   PDF

2. On the limitation of the global time assumption in distributed systems

   • Uri Abraham, Shai Ben-David, Shlomo Moran

   Pages 1-8

3. Causal memory

   • Mustaque Ahamad, James E. Burns, Phillip W. Hutto, Gil Neiger

   Pages 9-30

4. More on the power of random walks: Uniform self-stabilizing randomized algorithms

   • Efthymios Anagnostou, Ran El-Yaniv

   Pages 31-51

5. Pseudo read-modify-write operations: Bounded wait-free implementations

   • James H. Anderson, Bojan Grošelj

   Pages 52-70

6. Maintaining digital clocks in step

   • Anish Arora, Shlomi Dolev, Mohamed Gouda

   Pages 71-79

7. Implementing FIFO queues and stacks

   • Hagit Attiya

   Pages 80-94

8. Optimal amortized distributed consensus

   • Amotz Bar-Noy, Xiaotie Deng, Juan A. Garay, Tiko Kameda

   Pages 95-107

9. Optimally simulating crash failures in a byzantine environment

   • Rida Bazzi, Gil Neiger

   Pages 108-128

10. Efficient distributed consensus with n=(3 + ɛ)t processors

    • Piotr Berman, Juan A. Garay

    Pages 129-142

11. Randomized consensus in expected O(n²log n) operations

    • Gabi Bracha, Ophir Rachman

    Pages 143-150

12. Using adaptive timeouts to achieve at-most-once message delivery

    • Soma Chaudhuri, Brian A. Coan, Jennifer L. Welch

    Pages 151-166

13. Uniform dynamic self-stabilizing leader election

    • Shlomi Dolev, Amos Israeli, Shlomo Moran

    Pages 167-180

14. The quickest path problem in distributed computing systems

    • Yung-Chen Hung, Gen-Huey Chen

    Pages 181-192

15. The communication complexity of the two list problem

    • Alon Itai

    Pages 193-199

16. Distributed algorithms for updating shortest paths

    • Giuseppe F. Italiano

    Pages 200-211

17. Minimal shared information for concurrent reading and writing

    • Prasad Jayanti, Adarshpal Sethi, Errol L. Lloyd

    Pages 212-228

18. Reading many variables in one atomic operation solutions with linear or sublinear complexity

    • Lefteris M. Kirousis, Paul Spirakis, Philippas Tsigas

    Pages 229-241

19. Analysis of distributed algorithms based on recurrence relations

    • Yossi Malka, Sergio Rajsbaum

    Pages 242-253

20. Detection of global state predicates

    • Keith Marzullo, Gil Neiger

    Pages 254-272

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.

• Distributed Algorithms
• Distributed Graphs
• Distributed Networks
• Distributed Protocols
• Dsitributed Systems
• Verteilte Graphen
• Verteilte Netzwerke
• Verteilte Protokolle
• Verteilte Systeme
• algorithm
• algorithms
• algorithm analysis and problem complexity

Policies and ethics