Distributed Computing: 18th International Conference, DISC 2004, Amsterdam, The Netherlands, October 4-7, 2004. Proceedings

Achour Mostefaoui, Sergio Rajsbaum, Michel Raynal (auth.), Rachid Guerraoui (eds.)3540233067, 9783540233060, 9783540301868

This book constitutes the refereed proceedings of the 18th International Conference on Distributed Computing, DISC 2004, held in Amsterdam, The Netherlands, in October 2004.

The 31 revised full papers presented together with an extended abstract of an invited lecture and an eulogy for Peter Ruzicka were carefully reviewed and selected from 142 submissions. The entire scope of current issues in distributed computing is addressed, ranging from foundational and theoretical topics to algorithms and systems issues to applications in various fields.

---

Table of contents :
Front Matter….Pages –
The Synchronous Condition-Based Consensus Hierarchy….Pages 1-15
Synchronous Condition-Based Consensus Adapting to Input-Vector Legality….Pages 16-29
Group-Solvability….Pages 30-40
The Notion of Veto Number and the Respective Power of $Diamond {cal P}$ and $Diamond {cal S}$ to Solve One-Shot Agreement Problems….Pages 41-55
The Black-White Bakery Algorithm and Related Bounded-Space, Adaptive, Local-Spinning and FIFO Algorithms….Pages 56-70
Local-Spin Group Mutual Exclusion Algorithms….Pages 71-85
On Quorum Systems for Group Resources with Bounded Capacity….Pages 86-101
Bounded Version Vectors….Pages 102-116
An Optimistic Approach to Lock-Free FIFO Queues….Pages 117-131
A Single-Enqueuer Wait-Free Queue Implementation….Pages 132-143
Practical Lock-Free and Wait-Free LL/SC/VL Implementations Using 64-Bit CAS….Pages 144-158
Efficient Adaptive Collect Using Randomization….Pages 159-173
Nonblocking Concurrent Data Structures with Condition Synchronization….Pages 174-187
Dynamic Memory ABP Work-Stealing….Pages 188-200
Coupling and Self-stabilization….Pages 201-215
Optimal Randomized Self-stabilizing Mutual Exclusion on Synchronous Rings….Pages 216-229
Virtual Mobile Nodes for Mobile Ad Hoc Networks….Pages 230-244
Contention-Free MAC Protocols for Wireless Sensor Networks….Pages 245-259
Relationships Between Broadcast and Shared Memory in Reliable Anonymous Distributed Systems….Pages 260-274
A Local Algorithm for Ad Hoc Majority Voting via Charge Fusion….Pages 275-289
Message-Optimal and Latency-Optimal Termination Detection Algorithms for Arbitrary Topologies….Pages 290-304
Routing with Improved Communication-Space Trade-Off….Pages 305-319
Active and Concurrent Topology Maintenance….Pages 320-334
Distributed Weighted Matching….Pages 335-348
Exploiting Content Localities for Efficient Search in P2P Systems….Pages 349-364
Compact Routing Schemes for Bounded Tree-Length Graphs and for k -Chordal Graphs….Pages 365-378
Towards a Theory of Consistency Primitives….Pages 379-389
Fault-Tolerant Storage in a Dynamic Environment….Pages 390-404
Non-skipping Timestamps for Byzantine Data Storage Systems….Pages 405-419
Efficient Verification for Provably Secure Storage and Secret Sharing in Systems Where Half the Servers Are Faulty….Pages 420-434
Optimal Dispersal of Certificate Chains….Pages 435-449
On Byzantine Agreement over (2,3)-Uniform Hypergraphs….Pages 450-464
Back Matter….Pages –