Distributed Computing: 22nd International Symposium, DISC 2008, Arcachon, France, September 22-24, 2008. Proceedings

Front Matter....Pages -
The Mailbox Problem....Pages 1-15
Matrix Signatures: From MACs to Digital Signatures in Distributed Systems....Pages 16-31
How to Solve Consensus in the Smallest Window of Synchrony....Pages 32-46
Local Terminations and Distributed Computability in Anonymous Networks....Pages 47-62
A Self-stabilizing Algorithm with Tight Bounds for Mutual Exclusion on a Ring....Pages 63-77
Fast Distributed Approximations in Planar Graphs....Pages 78-92
Closing the Complexity Gap between FCFS Mutual Exclusion and Mutual Exclusion....Pages 93-108
The Weakest Failure Detector for Message Passing Set-Agreement....Pages 109-120
Local Maps: New Insights into Mobile Agent Algorithms....Pages 121-136
 r 3 : Resilient Random Regular Graphs....Pages 137-151
Online, Dynamic, and Distributed Embeddings of Approximate Ultrametrics....Pages 152-166
Constant-Space Localized Byzantine Consensus....Pages 167-181
Optimistic Erasure-Coded Distributed Storage....Pages 182-196
On the Emulation of Finite-Buffered Output Queued Switches Using Combined Input-Output Queuing....Pages 197-211
On Radio Broadcasting in Random Geometric Graphs....Pages 212-226
Ping Pong in Dangerous Graphs: Optimal Black Hole Search with Pure Tokens....Pages 227-241
Deterministic Rendezvous in Trees with Little Memory....Pages 242-256
Broadcasting in UDG Radio Networks with Missing and Inaccurate Information....Pages 257-273
Efficient Broadcasting in Known Geometric Radio Networks with Non-uniform Ranges....Pages 274-288
On the Robustness of (Semi) Fast Quorum-Based Implementations of Atomic Shared Memory....Pages 289-304
Permissiveness in Transactional Memories....Pages 305-319
The Synchronization Power of Coalesced Memory Accesses....Pages 320-334
Optimizing Threshold Protocols in Adversarial Structures....Pages 335-349
Hopscotch Hashing....Pages 350-364
Computing Lightweight Spanners Locally....Pages 365-378
Dynamic Routing and Location Services in Metrics of Low Doubling Dimension....Pages 379-393
Leveraging Linial’s Locality Limit....Pages 394-407
Continuous Consensus with Failures and Recoveries....Pages 408-422
No Double Discount: Condition-Based Simultaneity Yields Limited Gain....Pages 423-437
Bosco: One-Step Byzantine Asynchronous Consensus....Pages 438-450
A Limit to the Power of Multiple Nucleation in Self-assembly....Pages 451-465
Using Bounded Model Checking to Verify Consensus Algorithms....Pages 466-480
Theoretical Bound and Practical Analysis of Connected Dominating Set in Ad Hoc and Sensor Networks....Pages 481-495
Brief Announcement: On the Solvability of Anonymous Partial Grids Exploration by Mobile Robots....Pages 496-497
The Dynamics of Probabilistic Population Protocols....Pages 498-499
A Distributed Algorithm for Computing and Updating the Process Number of a Forest....Pages 500-501
 Brief Announcment: Corruption Resilient Fountain Codes....Pages 502-503
Brief Announcement: An Early-Stopping Protocol for Computing Aggregate Functions in Sensor Networks....Pages 504-506
Easy Consensus Algorithms for the Crash-Recovery Model....Pages 507-508
Evaluating the Quality of a Network Topology through Random Walks....Pages 509-511
Brief Announcement: Local-Spin Algorithms for Abortable Mutual Exclusion and Related Problems....Pages 512-513
Data Failures....Pages 514-515
Reliable Broadcast Tolerating Byzantine Faults in a Message-Bounded Radio Network....Pages 516-517
Brief Announcement: Eventual Leader Election in the Infinite Arrival Message-Passing System Model....Pages 518-519
Back Matter....Pages -