Distributed Algorithms: 10th International Workshop, WDAG ’96 Bologna, Italy, October 9–11, 1996 Proceedings

Butler W. Lampson (auth.), Özalp Babaoğlu, Keith Marzullo (eds.)3540617698, 9783540617693

This book constitutes the refereed proceedings of the 10th International Workshop on Distributed Algorithms, WDAG ’96, held in Bologna, Italy, in October 1996.
The volume presents 21 revised full papers selected from 75 submissions together with invited contributions by Butler Lampson and Domenico Ferrari. The volume reflects the transition of the area from formerly being the domain of a small research community to becoming the dominant computing paradigm and an industrial technology. Among the topics covered are all current aspects of distributed algorithms ranging from theory to applications such as distributed intelligent agents.

---

Table of contents :
How to build a highly available system using consensus….Pages 1-17
Distributed admission control algorithms for real-time communication….Pages 18-28
Randomization and failure detection: A hybrid approach to solve Consensus….Pages 29-39
Levels of authentication in distributed agreement….Pages 40-55
Efficient and robust sharing of memory in message-passing systems….Pages 56-70
Plausible clocks: Constant size logical clocks for Distributed Systems….Pages 71-88
Abstracting communication to reason about distributed algorithms….Pages 89-104
Simulating reliable links with unreliable links in the presence of process crashes….Pages 105-122
A cyclic distributed garbage collector for network objects….Pages 123-140
Incremental, distributed orphan detection and actor garbage collection using graph partitioning and euler cycles….Pages 141-158
A framework for the analysis of non-deterministic clock synchronisation algorithms….Pages 159-174
Optimal time broadcasting in faulty star networks….Pages 175-190
A lower bound for Linear Interval Routing….Pages 191-205
Topological routing schemes….Pages 206-219
Maintaining a dynamic set of processors in a distributed system….Pages 220-233
Collective consistency….Pages 234-250
Planar quorums….Pages 251-268
“Γ-accurate” failure detectors….Pages 269-286
Fast, long-lived renaming improved and simplified….Pages 287-303
A timestamp based transformation of self-stabilizing programs for distributed computing environments….Pages 304-321
The combinatorial structure of wait-free solvable tasks….Pages 322-343
Understanding the Set Consensus Partial Order using the Borowsky-Gafni Simulation….Pages 344-361
….Pages 362-379