## Distributed Algorithms: 4th International Workshop, Bari, Italy, September 24-26, 1990. Proceedings.Jan Leeuwen, Jan van Leeuwen, Nicola Santoro, Università di Bari. Istituto di scienze dell'informazione 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

SelfStabilizing Ring Orientation | 1 |

MemoryEfficient Self Stabilizing Protocols for General Networks | 15 |

On the Computational Power Needed to Elect a Leader | 29 |

Spanning Tree Construction for Nameless Networks | 41 |

A linear faulttolerant naming algorithm | 57 |

A ComplexityOriented View | 71 |

An Improved Algorithm to Detect Communication Deadlocks in Distributed Systems | 90 |

On the Average Performance of Synchronized Programs in Distributed Networks | 102 |

LocalizedAccess Protocols for Replicated Databases | 245 |

WEIGHTED VOTING FOR OPERATION DEPENDENT MANAGEMENT OF REPLICATED DATA | 263 |

Wakeup under ReadWrite Atomicity | 277 |

Time and Message Efficient Reliable Broadcasts | 289 |

EarlyStopping Distributed Bidding and Applications | 304 |

FAST CONSENSUS IN NETWORKS OF BOUNDED DEGREE | 321 |

Common Knowledge and Consistent Simultaneous Coordination | 334 |

Agreement on the Group Membership in Synchronous Distributed Systems | 353 |

Distributed Algorithms for Reconstructing MST after Topology Change | 122 |

EFFICIENT DISTRIBUTED ALGORITHMS FOR SINGLESOURCE SHORTEST PATHS AND RELATED PROBLEMS ON PLANE NETWORKS | 133 |

Stepwise Development of a Distributed Load Balancing Algorithm | 151 |

Greedy Packet Scheduling | 169 |

Optimal Computation of Global Sensitive Functions in Fast Networks | 185 |

Efficient Mechanism for Fairness and DeadlockAvoidance in HighSpeed Networks | 192 |

Strong Verifiable Secret Sharing Extended Abstract | 213 |

WEAK CONSISTENCY AND PESSIMISTIC REPLICA CONTROL | 228 |

TIGHT BOUNDS ON THE ROUND COMPLEXITY OF DISTRIBUTED 1SOLVABLE TASKS | 373 |

A TimeRandomness Tradeoff for Communication Complexity | 390 |

BOUNDS ON THE COSTS OF REGISTER IMPLEMENTATIONS | 402 |

A Bounded FirstIn FirstEnabled Solution to the 1Exclusion Problem | 422 |

LIST OF PARTICIPANTS | 432 |

433 | |

### Common terms and phrases

action assume atomic Atomic Broadcast binary bits common knowledge communication complexity Computer Science concurrency control concurrent configuration connected component consensus consider coordinator copies correct processes corresponding crash cycle data structure Database defined definition deleted denote distributed algorithm Distributed Bidding Distributed Computing distributed system edge execution exists failures faulty processors fully connected networks function global graph greedy algorithm hypercube IEEE implement initial Lemma logical logn lower bound message complexity neighbor NextState node nonfaulty processors number of messages operation outerplane packet partition perform phase physical registers Proc Proof protocol random received Reliable Broadcast replicated request requires root round routing SAT-MRG schedule self-stabilizing sequence number serializability shortest path spanning tree synchronous termination Theorem timestamp token topology transactions transition traversal updated upper bound variables Verifiable Secret Sharing wakeup write