Gafni E., Santoro N. Distributed Algorithms on Graphs

McGill-Queen's University Press, 1986. — 203 p.This volume contains papers presented at the First International Workshop on Distributed Algorithms. The papers present solutions to a wide spectrum of problems (leader election, resource allocation, routing, etc.) and focus on a variety of issues that influence communications complexity.The bit complexity of probabilistic leader election on a unidirectional ring.
Minimizing a virtual control token ring.
New upper bounds for decentralized extrema-finding in a ring of processors.
Efficient algorithms for routing information in a multicomputer system.
Lower bounds on common knowledge in distributed algorithms.
Scheme for efficiency-performance measures of distributed and parallel algorithms.
Duplicate routing in distributed networks.
Notes on distributed algorithms in unidirectional rings.
Sense of direction and communication complexity in distributed networks.
The communication complexity hierarchy in distributed computing.
Simulation of chaotic algorithms by token algorithms.
A general distributed graph algorithm for fair access to critical sections.
ADDENDA.
a. Open Problems.
b. A bibliography of distributed algorithms (1985).
c. Author Index.