Distributed Computing: 19th International Conference, DISC 2005, Cracow, Poland, September 26-29, 2005. Proceedings

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 -