Distributed algorithms on graphs : proceedings of the 1st International Workshop on Distributed Algorithms : Ottawa, Canada, August 1985 / edited by Eli Gafni and Nicola Santoro
Contents -- 1. The bit complexity of probabilistic leader election on a unidirectional ring -- 2. Minimizing a virtual control token ring -- 3. New upperbounds for decentralized extrema-finding in a ring of processors -- 4. Efficient algorithms for routing information in a multicomputer system -- 5. Lower bounds on common knowledge in distributed algorithms -- 6. Scheme for efficiency-performance measures of distributed and parallel algorithms -- 7.* Distributed clock synchronization -- 8. Duplicate routing in distributed networks
9. Notes on distributed algorithms in unidirectional rings10. Sense of direction and communication complexity in distributed networks -- 11. The communication complexity hierarchy in distributed computing -- 12. Simulation of chaotic algorithms by token algorithms -- 13. A general distributed graph algorithm for fair access to critical sections -- ADDENDA -- a. Open Problems -- b. A bibliography of distributed algorithms -- c. Author Index
