This book constitutes the refereed proceedings of the 19th International Conference on Distributed Computing, DISC 2005, held in Cracow, Poland, in September 2005.
The 32 revised full papers selected from 162 submissions are presented together with 14 brief announcements of ongoing works chosen from 30 submissions; all of them were carefully selected for inclusion in the book. The entire scope of current issues in distributed computing is addressed, ranging from foundational and theoretical topics to algorithms and systems issues and to applications in various fields.
Author(s): Michael Mitzenmacher (auth.), Pierre Fraigniaud (eds.)
Series: Lecture Notes in Computer Science 3724 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2005
Language: English
Pages: 522
Tags: Computer Communication Networks; Algorithm Analysis and Problem Complexity; Programming Techniques; Computation by Abstract Devices; Operating Systems
Front Matter....Pages -
Digital Fountains and Their Application to Informed Content Delivery over Adaptive Overlay Networks....Pages 1-1
Securing the Net: Challenges, Failures and Directions....Pages 2-2
Coterie Availability in Sites....Pages 3-17
Keeping Denial-of-Service Attackers in the Dark....Pages 18-32
On Conspiracies and Hyperfairness in Distributed Computing....Pages 33-47
On the Availability of Non-strict Quorum Systems....Pages 48-62
Musical Benches....Pages 63-77
Obstruction-Free Algorithms Can Be Practically Wait-Free....Pages 78-92
Efficient Reduction for Wait-Free Termination Detection in a Crash-Prone Distributed System....Pages 93-107
Non-blocking Hashtables with Open Addressing....Pages 108-121
Computing with Reads and Writes in the Absence of Step Contention....Pages 122-136
Restricted Stack Implementations....Pages 137-151
Proving Atomicity: An Assertional Approach....Pages 152-168
Time and Space Lower Bounds for Implementations Using k -CAS....Pages 169-183
(Almost) All Objects Are Universal in Message Passing Systems....Pages 184-198
Ω Meets Paxos: Leader Election and Stability Without Eventual Timely Links....Pages 199-213
Plausible Clocks with Bounded Inaccuracy....Pages 214-228
Causing Communication Closure: Safe Program Composition with Non-FIFO Channels....Pages 229-243
What Can Be Implemented Anonymously?....Pages 244-259
Waking Up Anonymous Ad Hoc Radio Networks....Pages 260-272
Fast Deterministic Distributed Maximal Independent Set Computation on Growth-Bounded Graphs....Pages 273-287
Distributed Computing with Imperfect Randomness....Pages 288-302
Polymorphic Contention Management....Pages 303-323
Distributed Transactional Memory for Metric-Space Networks....Pages 324-338
Concise Version Vectors in WinFS....Pages 339-353
Adaptive Software Transactional Memory....Pages 354-368
Optimistic Generic Broadcast....Pages 369-383
Space and Step Complexity Efficient Adaptive Collect....Pages 384-398
Observing Locally Self-stabilization in a Probabilistic Way....Pages 399-413
Asymptotically Optimal Solutions for Small World Graphs....Pages 414-428
Deciding Stability in Packet-Switched FIFO Networks Under the Adversarial Queuing Model in Polynomial Time , ....Pages 429-441
Compact Routing for Graphs Excluding a Fixed Minor....Pages 442-456
General Compact Labeling Schemes for Dynamic Trees....Pages 457-471
The Dynamic And-Or Quorum System....Pages 472-486
Byzantine Clients Rendered Harmless....Pages 487-489
Reliably Executing Tasks in the Presence of Malicious Processors....Pages 490-492
Obstruction-Free Step Complexity: Lock-Free DCAS as an Example....Pages 493-494
Communication-Efficient Implementation of Failure Detector Classes $\diamondsuit\mathcal{Q}$ and $\diamondsuit\mathcal{P}$ ....Pages 495-496
Optimal Resilience for Erasure-Coded Byzantine Distributed Storage....Pages 497-498
Agreement Among Unacquainted Byzantine Generals....Pages 499-500
Subscription Propagation and Content-Based Routing with Delivery Guarantees....Pages 501-502
Asynchronous Verifiable Information Dispersal....Pages 503-504
Towards a Theory of Self-organization....Pages 505-506
Timing Games and Shared Memory....Pages 507-508
A Lightweight Group Mutual k -Exclusion Algorithm Using Bi- k -Arbiters....Pages 509-510
Could any Graph be Turned into a Small-World?....Pages 511-513
Papillon: Greedy Routing in Rings....Pages 514-515
An Efficient Long-Lived Adaptive Collect Algorithm....Pages 516-518
Back Matter....Pages -
