Distributed Computing: 23rd International Symposium, DISC 2009, Elche, Spain, September 23-25, 2009. Proceedings

Front Matter....Pages -
The 2009 Edsger W. Dijkstra Prize in Distributed Computing....Pages 1-2
Computing, Observing, Controlling, Checkpointing: Symbiosis Is Even Better Than Agreement!....Pages 3-4
What Agreement Problems Owe Michel....Pages 5-5
Shmuel Zaks - The Early Years: A Combinatorialist in Distributed Computing....Pages 6-6
Shmuel Zaks - The Mathematician, Computer Scientist and Personality....Pages 7-7
The Disagreement Power of an Adversary....Pages 8-21
New Bounds for the Controller Problem....Pages 22-34
On Set Consensus Numbers....Pages 35-47
The Abstract MAC Layer....Pages 48-62
Randomization Can Be a Healer: Consensus with Dynamic Omission Failures....Pages 63-77
Interrupting Snapshots and the Java $^{\mbox{\tiny TM}}$ Size() Method....Pages 78-92
Elastic Transactions....Pages 93-107
Brief Announcement: Transactional Scheduling for Read-Dominated Workloads....Pages 108-110
Tight Group Renaming on Groups of Size g Is Equivalent to g-Consensus....Pages 111-126
The RedBlue Adaptive Universal Constructions....Pages 127-141
Help When Needed, But No More: Efficient Read/Write Partial Snapshot....Pages 142-156
Contention-Sensitive Data Structures and Algorithms....Pages 157-171
Brief Announcement: Acceleration by Contention for Shared Memory Mutual Exclusion Algorithms....Pages 172-173
Brief Announcement: Incremental Component-Based Modeling, Verification, and Performance Evaluation of Distributed Reset....Pages 174-175
Local Computation of Nearly Additive Spanners....Pages 176-190
A Local 2-Approximation Algorithm for the Vertex Cover Problem....Pages 191-205
Distributed Discovery of Large Near-Cliques....Pages 206-220
Distributed Fractional Packing and Maximum Weighted b-Matching via Tail-Recursive Duality....Pages 221-238
Brief Announcement: Decidable Graph Languages by Mediated Population Protocols....Pages 239-240
Brief Announcement: Towards Secured Distributed Polling in Social Networks....Pages 241-242
What Can Be Observed Locally?....Pages 243-257
At-Most-Once Semantics in Asynchronous Shared Memory....Pages 258-273
Nonblocking Algorithms and Backward Simulation....Pages 274-288
Brief Announcement: Efficient Model Checking of Fault-Tolerant Distributed Protocols Using Symmetry Reduction....Pages 289-290
Brief Announcement: Dynamic FTSS in Asynchronous Systems: The Case of Unison....Pages 291-293
Dynamics in Network Interaction Games....Pages 294-308
Brief Announcement: Cloud Computing Games: Pricing Services of Large Data Centers....Pages 309-310
On the Existence of Weakest Failure Detectors for Mutual Exclusion and k -Exclusion....Pages 311-325
Crash-Quiescent Failure Detection....Pages 326-340
The Price of Anonymity: Optimal Consensus Despite Asynchrony, Crash and Anonymity....Pages 341-355
Brief Announcement: On Implementing Omega Efficiently in the Crash-Recovery Model....Pages 356-357
Brief Announcement: The Minimum Failure Detector for Non-Local Tasks in Message-Passing Systems....Pages 358-359
Brief Announcement: Weak Synchrony Models and Failure Detectors for Message Passing ( k -)Set Agreement....Pages 360-361
Brief Announcement Zab: A Practical Totally Ordered Broadcast Protocol....Pages 362-363
Compact Multicast Routing....Pages 364-378
Compact Routing in Power-Law Graphs....Pages 379-391
Virtual Ring Routing Trends....Pages 392-406
A New Self-stabilizing Minimum Spanning Tree Construction with Loop-Free Property....Pages 407-422
Euler Tour Lock-In Problem in the Rotor-Router Model....Pages 423-435
Optimum Simultaneous Consensus for General Omissions Is Equivalent to an NP Oracle....Pages 436-448
On the Number of Synchronous Rounds Sufficient for Authenticated Byzantine Agreement....Pages 449-463
From Almost Everywhere to Everywhere: Byzantine Agreement with $\tilde{O}(n^{3/2})$ Bits....Pages 464-478
Brief Announcement: A Leader-free Byzantine Consensus Algorithm....Pages 479-480
Efficient k-Shot Broadcasting in Radio Networks....Pages 481-495
Keeping Mobile Robot Swarms Connected....Pages 496-511
Consensus and Mutual Exclusion in a Multiple Access Channel....Pages 512-526
Brief Announcement: Efficient Utilization of Multiple Interfaces in Wireless Ad Hoc Networks....Pages 527-528
Brief Announcement: The Speed of Broadcasting in Random Networks – Density Does Not Matter....Pages 529-530
Back Matter....Pages -