Distributed Algorithms

1. Front Matter

   PDF

2. Sparser: A paradigm for running distributed algorithms

   • Yehuda Afek, Moty Ricklin

   Pages 1-10

3. Closed schedulers: Constructions and applications to consensus protocols

   • Ronit Lubitch, Shlomo Moran

   Pages 11-34

4. Efficient atomic snapshots using lattice agreement

   • Hagit Attiya, Maurice Herlihy, Ophir Rachman

   Pages 35-53

5. Choice coordination with multiple alternatives (preliminary version)

   • David S. Greenberg, Gadi Taubenfeld, Da-Wei Wang

   Pages 54-68

6. Some results on the impossibility, universality, and decidability of consensus

   • Prasad Jayanti, Sam Toueg

   Pages 69-84

7. Wait-free test-and-set

   • Yehuda Afek, Eli Gafni, John Tromp, Paul M. B. Vitanyi

   Pages 85-94

8. A concurrent time-stamp scheme which is linear in time and space

   • Amos Israeli, Meir Pinhasov

   Pages 95-109

9. Tentative and definite distributed computations: An optimistic approach to network synchronization

   • J. Garofalakis, S. Rajsbaum, P. Spirakis, B. Tampakas

   Pages 110-119

10. Semisynchrony and real time

    • Stephen Ponzio, Ray Strong

    Pages 120-135

11. Optimal time Byzantine agreement for t < n/8 with linear messages

    • Arkady Zamsky, Amos Israeli, Shlomit S. Pinter

    Pages 136-152

12. A continuum of failure models for distributed computing

    • Juan A. Garay, Kenneth J. Perry

    Pages 153-165

13. Simulating crash failures with many faulty processors (extended abstract)

    • Rida Bazzi, Gil Neiger

    Pages 166-184

14. An efficient topology update protocol for dynamic networks

    • Baruch Awerbuch, Yishay Mansour

    Pages 185-202

15. Memory adaptive self-stabilizing protocols (extended abstract)

    • Efthymios Anagnostou, Ran El-Yaniv, Vassos Hadzilacos

    Pages 203-220

16. Optimal early stopping in distributed consensus

    • Piotr Berman, Juan A. Garay, Kenneth J. Perry

    Pages 221-237

17. Traffic-light scheduling on the grid

    • Guy Kortsarz, David Peleg

    Pages 238-252

18. Distributed computing on anonymous hypercubes with faulty components

    • Evangelos Kranakis, Nicola Santoro

    Pages 253-263

19. Message terminate algorithms for anonymous rings of unknown size

    • Israel Cidon, Yuval Shavitt

    Pages 264-276

20. Distributed resource allocation algorithms

    • Judit Bar-Ilan, David Peleg

    Pages 277-291

This volume presents the proceedings of the Sixth Workshop on Distributed Algorithms (WDAG 92), held in Haifa, Israel, November 2-4, 1992. WDAG provides a forum for researchers and other parties interested in distributedalgorithms and their applications. The aim is to present recent research results, explore directions for future research, and identify common fundamental techniques that serve as building blocks in many distributed algorithms. Papers in the volume describe original results in all areas of distributed algorithms and their applications, including distributed graph algorithms, distributed combinatorial algorithms, design of network protocols, routing and flow control, communication complexity, fault-tolerant distributed algorithms, distributed data structures, distributed database techniques, replica control protocols, distributed optimization algorithms, mechanisms for safety and security in distributed systems, and protocols for real-time distributed systems.

• Algorithms
• Routing
• algorithm
• complexity
• data structure
• distributed systems
• optimization
• real-time
• security
• algorithm analysis and problem complexity

Policies and ethics