Distributed Algorithms: 6th International Workshop, WDAG ’92 Haifa, Israel, November 2–4, 1992 Proceedings

Yehuda Afek, Moty Ricklin (auth.), Adrian Segall, Shmuel Zaks (eds.)3540561889, 9783540561880

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.

---

Table of contents :
Sparser: A paradigm for running distributed algorithms….Pages 1-10
Closed schedulers: Constructions and applications to consensus protocols….Pages 11-34
Efficient atomic snapshots using lattice agreement….Pages 35-53
Choice coordination with multiple alternatives (preliminary version)….Pages 54-68
Some results on the impossibility, universality, and decidability of consensus….Pages 69-84
Wait-free test-and-set….Pages 85-94
A concurrent time-stamp scheme which is linear in time and space….Pages 95-109
Tentative and definite distributed computations: An optimistic approach to network synchronization….Pages 110-119
Semisynchrony and real time….Pages 120-135
Optimal time Byzantine agreement for t < n /8 with linear messages….Pages 136-152
A continuum of failure models for distributed computing….Pages 153-165
Simulating crash failures with many faulty processors (extended abstract)….Pages 166-184
An efficient topology update protocol for dynamic networks….Pages 185-202
Memory adaptive self-stabilizing protocols (extended abstract)….Pages 203-220
Optimal early stopping in distributed consensus….Pages 221-237
Traffic-light scheduling on the grid….Pages 238-252
Distributed computing on anonymous hypercubes with faulty components….Pages 253-263
Message terminate algorithms for anonymous rings of unknown size….Pages 264-276
Distributed resource allocation algorithms….Pages 277-291
Membership algorithms for multicast communication groups….Pages 292-312
The granularity of waiting (extended Abstract)….Pages 313-328
The cost of order in asynchronous systems….Pages 329-345
Efficient, strongly consistent implementations of shared memory….Pages 346-361
Optimal primary-backup protocols….Pages 362-378