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

by Taubenfeld, Gadi

• ISBN13: 9783540877783
• ISBN10: 3540877789
• Format: Paperback
• Copyright: 2008-12-31
• Publisher: Springer-Verlag New York Inc

Summary

This book constitutes the refereed proceedings of the 22nd International Symposium on Distributed Computing, DISC 2008, held in Arcachon, France, in September 2008. The 33 revised full papers, selected from 101 submissions, are presented together with 11 brief announcements of ongoing works; all of them were carefully reviewed and selected for inclusion in the book. The papers address all aspects of distributed computing, including the theory, design, implementation and applications of distributed algorithms, systems and networks - ranging from foundational and theoretical topics to algorithms and systems issues and to applications in various fields.

Table of Contents

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