Distributed Algorithms: 7th International Workshop, WDAG’93 Lausanne, Switzerland, September 27–29, 1993 Proceedings

Amos Israeli, Lihu Rappoport (auth.), André Schiper (eds.)3540572716, 9783540572718

This volume presents the proceedings of the Seventh International Workshop on Distributed Algorithms (WDAG 93), held in Lausanne, Switzerland, September 1993. It contains 22 papers selected from 72 submissions. The selection was based on originality, quality, and relevance to the field of distributed computing: 6 papers are from Europe, 13 from North America, and 3 from the Middle East. The papers discuss topics from all areas of distributed computing and their applications, including distributed algorithms for control and communication, fault-tolerant distributed algorithms, network protocols, algorithms for managing replicated data, protocols for real-time distributed systems, issues of asynchrony, synchrony and real-time, mechanisms for security in distributed systems, techniques for the design and analysis of distributed algorithms, distributed database techniques, distributed combinatorial and optimization algorithms, and distributed graph algorithms.

---

Table of contents :
Efficient wait-free implementation of a concurrent priority queue….Pages 1-17
Binary snapshots….Pages 18-25
Linear-time snapshot protocols for unbalanced systems….Pages 26-38
Towards a necessary and sufficient condition for wait-free synchronization (Extended Abstract)….Pages 39-53
Efficient algorithms for checking the atomicity of a run of read and write operations….Pages 54-68
Benign failure models for shared memory….Pages 69-83
Generalized agreement between concurrent fail-stop processes….Pages 84-98
Controlling memory access concurrency in efficient fault-tolerant parallel algorithms (extended abstract)….Pages 99-114
Asynchronous epoch management in replicated databases….Pages 115-128
Crash resilient communication in dynamic networks….Pages 129-144
Distributed job scheduling using snapshots….Pages 145-159
Optimal time self stabilization in dynamic systems….Pages 160-173
Tolerating transient and permanent failures (extended abstract)….Pages 174-188
Quick atomic broadcast….Pages 189-203
Time bounds for decision problems in the presence of timing uncertainty and failures….Pages 204-218
Boolean Routing….Pages 219-233
Notes on sorting and counting networks (extended abstract)….Pages 234-248
A simple, efficient algorithm for maximum finding on rings….Pages 249-263
Wang tilings and distributed orientation on anonymous torus networks (extended abstract)….Pages 264-278
Fairness of N-party synchronization and its implementation in a distributed environment….Pages 279-293
Programming distributed reactive systems: A strong and weak synchronous coupling….Pages 294-308
Using message semantics to reduce rollback in the time warp mechanism….Pages 309-323