Distributed Algorithms: 4th International Workshop Bari, Italy, September 24–26, 1990 Proceedings

Amos Israeli, Marc Jalfon (auth.), Jan van Leeuwen, Nicola Santoro (eds.)3540540997, 9783540540991

This volume contains the proceedings of the 4th International Workshop on Distributed Algorithms, held near Bari, Italy, September 24-26, 1990. The workshop was a forum for researchers, students and other interested persons to discuss recent results and trends in the design and analysis of distributed algorithms for communication networks and decentralized systems. The volume includes all 28 papers presented at the workshop, covering current research in such aspects of distributed algorithm design as distributed combinatorial algorithms, distributed algorithms on graphs, distributed algorithms for new types of decentralized systems, distributed data structures, synchronization and load-balancing, distributed algorithms for control and communication, design and verification of network protocols, routing algorithms, fail-safe and fault-tolerant distributed algorithms, distributed database techniques, algorithms for transaction management and replica control, and other related topics.

---

Table of contents :
Self-stabilizing ring orientation….Pages 1-14
Memory-efficient self stabilizing protocols for general networks….Pages 15-28
On the computational power needed to elect a leader….Pages 29-40
Spanning tree construction for nameless networks….Pages 41-56
A linear fault-tolerant naming algorithm….Pages 57-70
Distributed data structures: A complexity-oriented view….Pages 71-89
An improved algorithm to detect communication deadlocks in distributed systems….Pages 90-101
On the average performance of synchronized programs in distributed networks….Pages 102-121
Distributed algorithms for reconstructing MST after topology change….Pages 122-132
Efficient distributed algorithms for single-source shortest paths and related problems on plane networks….Pages 133-150
Stepwise development of a distributed load balancing algorithm….Pages 151-168
Greedy packet scheduling….Pages 169-184
Optimal computation of global sensitive functions in fast networks….Pages 185-191
Efficient mechanism for fairness and deadlock-avoidance in high-speed networks….Pages 192-212
Strong verifiable secret sharing extended abstract….Pages 213-227
Weak consistency and pessimistic replica control….Pages 228-244
Localized-access protocols for replicated databases….Pages 245-262
Weighted voting for operation dependent management of replicated data….Pages 263-276
Wakeup under read/write atomicity….Pages 277-288
Time and message efficient reliable broadcasts….Pages 289-303
Early-stopping distributed bidding and applications….Pages 304-320
Fast consensus in networks of bounded degree….Pages 321-333
Common knowledge and consistent simultaneous coordination….Pages 334-352
Agreement on the group membership in synchronous distributed systems….Pages 353-372
Tight bounds on the round complexity of distributed 1-solvable tasks….Pages 373-389
A time-randomness tradeoff for communication complexity….Pages 390-401
Bounds on the costs of register implementations….Pages 402-421
A bounded first-in, first-enabled solution to the l-exclusion problem….Pages 422-431