Distributed Computing: 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-8, 2004. ProceedingsRachid Guerraoui DISC, the International Symposium on Distributed Computing, is an annual conference for the presentation of research on the theory, design, analysis, implementation, and application of distributed systems and network. DISC 2004 was held on October 4-7, 2004, in Amsterdam, The Netherlands. There were 142 papers submitted to DISC this year. These were read and evaluated by the program committee members, assisted by external reviewers. The quality of submissions was high and we were unable to accept many dese- ing papers. Thirty one papers were selected at the program committee meeting in Lausanne to be included in these proceedings. The proceedings include an extended abstract of the invited talk by Ueli Maurer. In addition, they include a eulogy for Peter Ruzicka by Shmuel Zaks. The Best Student Paper Award was split and given to two papers: the paper “Efficient Adaptive Collect Using Randomization”, co-authored by Hagit Attiya, Fabian Kuhn, Mirjam Wattenhofer and Roger Wattenhofer, and the paper “Coupling and Self-stabilization”,co-authored by Laurent Fribourg, Stephane Messika and Claudine Picaronny. The support of the CWI and EPFL is gratefully acknowledged. The review process and the preparation of this volume were done using CyberChairPRO. I also thank Sebastien Baehni and Sidath Handurukande for their crucial help with these matters. August 2004 Rachid Guerraoui Peter Ruzicka 1947-2003 Peter died on Sunday, October 5, 2003, at the age of 56, after a short disease. He was a Professor of Informatics at the Faculty of Mathematics, Physics and Informatics in Comenius University, Bratislava, Slovakia. Those of us who knew him through DISC and other occasions mourn his death and cherish his memory |
Contents
1 | |
16 | |
GroupSolvability | 30 |
The BlackWhite Bakery Algorithm and Related BoundedSpace | 56 |
LocalSpin Group Mutual Exclusion Algorithms | 71 |
On Quorum Systems for Group Resources with Bounded Capacity | 86 |
Bounded Version Vectors | 102 |
An Optimistic Approach to LockFree FIFO Queues | 117 |
Relationships Between Broadcast and Shared Memory | 260 |
A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion | 275 |
MessageOptimal and LatencyOptimal Termination Detection Algorithms | 290 |
Routing with Improved CommunicationSpace TradeOff | 305 |
Active and Concurrent Topology Maintenance | 320 |
Distributed Weighted Matching | 335 |
Exploiting Content Localities for Efficient Search in P2P Systems | 349 |
Compact Routing Schemes for Bounded TreeLength Graphs | 365 |
A SingleEnqueuer WaitFree Queue Implementation | 132 |
Efficient Adaptive Collect Using Randomization | 159 |
Nonblocking Concurrent Data Structures with Condition Synchronization | 174 |
Dynamic Memory ABP WorkStealing | 188 |
Coupling and Selfstabilization | 201 |
Optimal Randomized Selfstabilizing Mutual Exclusion | 216 |
Virtual Mobile Nodes for Mobile Ad Hoc Networks | 230 |
ContentionFree MAC Protocols for Wireless Sensor Networks | 245 |
Towards a Theory of Consistency Primitives | 379 |
Nonskipping Timestamps for Byzantine Data Storage Systems | 405 |
Efficient Verification for Provably Secure Storage | 420 |
Optimal Dispersal of Certificate Chains | 435 |
On Byzantine Agreement over 23Uniform Hypergraphs | 450 |
465 | |
Other editions - View all
Distributed Computing: 18th International Conference, DISC 2004 ..., Volume 18 Rachid Guerraoui No preview available - 2004 |
Common terms and phrases
3-hyperedges ACM Symposium adaptive adversary application message assume asynchronous system atomic bits bounded broadcast Byzantine agreement Byzantine failures chain set client concurrent condition consensus consistency correct counter crash data structure defined denote deque dequeue distributed algorithm Distributed Computing distributed systems dynamic edge enqueue ergodic set execution expp,i failure detectors FIFO hazard pointer hypergraph implementation initial input vector integer Lemma linearizable linearization point LL/SC/VL local-spinning lock-free logn Markov chain memory mobile nodes Mobile Point mutual exclusion neighbors node number of processes object operation output peer-to-peer peers performance processors Proof properties protocol query queue quorum systems random request requires round routing scheme satisfies secret sharing Section self-stabilizing servers shared shared-memory simulate slot solvable step complexity storage system stored synchronous termination detection algorithm Theorem thread topology tree update variable version vectors vertex wait-free write