Distributed Algorithms: 3rd International Workshop Nice, France, September 26–28, 1989 Proceedings

Judit Bar-Ilan, Dror Zernik (auth.), Jean-Claude Bermond, Michel Raynal (eds.)3540516875, 9783540516873

This book includes the papers presented at the Third International Workshop on Distributed Algorithms organized at La Colle-sur-Loup, near Nice, France, September 26-28, 1989 which followed the first two successful international workshops in Ottawa (1985) and Amsterdam (1987). This workshop provided a forum for researchers and others interested in distributed algorithms on communication networks, graphs, 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. Papers describe original results in all areas of distributed algorithms and their applications, including: distributed combinatorial algorithms, distributed graph algorithms, distributed algorithms for control and communication, distributed database techniques, distributed algorithms for decentralized systems, fail-safe and fault-tolerant distributed algorithms, distributed optimization algorithms, routing algorithms, design of network protocols, algorithms for transaction management, composition of distributed algorithms, and analysis of distributed algorithms.

---

Table of contents :
Random leaders and random spanning trees….Pages 1-12
Fault-tolerant critical section management in asynchronous networks….Pages 13-23
Efficient emulation of single-hop radio network with collision detection on multi-hop radio network with no collision detection….Pages 24-32
Applying a path-compression technique to obtain an efficient distributed mutual exclusion algorithm….Pages 33-44
Combinatorics and geometry of consistent cuts : Application to concurrency theory….Pages 45-56
Distributed fairness algorithms for local area networks with concurrent transmissions….Pages 57-69
An efficient reliable ring protocol….Pages 70-82
An efficient solution to the drinking philosophers problem and its extensions….Pages 83-93
Highly concurrent logically synchronous multicast….Pages 94-109
Reliable broadcast in synchronous and asynchronous environments (preliminary version)….Pages 110-123
Observing global states of asynchronous distributed applications….Pages 124-135
Building a global time on parallel machines….Pages 136-147
Functional dependencies of variables in wait-free programs….Pages 148-159
Two strategies for solving the vertex cover problem on a transputer network….Pages 160-170
Optimal fault-tolerant distributed algorithms for election in complete networks with a global sense of direction….Pages 171-182
Simple and efficient election algorithms for anonymous networks….Pages 183-194
A distributed solution for detecting deadlock in distributed nested transaction systems….Pages 195-206
Distributed deadlock detection and resolution with probes….Pages 207-218
A new algorithm to implement causal ordering….Pages 219-232
Symmetry breaking in asynchronous rings with o(n) messages….Pages 233-241
Designing distributed algorithms by means of formal sequentially phased reasoning….Pages 242-253
Possibility and impossibility results in a shared memory environment….Pages 254-267
Communication heuristics in distributed combinatorial search algorithms….Pages 268-279
The role of inhibition in asynchronous consistent-cut protocols….Pages 280-291
How to construct an atomic variable (extended abstract)….Pages 292-302
Electing a leader when processor identity numbers are not distinct (extended abstract)….Pages 303-314