This book constitutes the refereed proceedings of the 23nd International Symposium on Distributed Computing, DISC 2009, held in Elche, Spain, in September 2009.
The 33 revised full papers, selected from 121 submissions, are presented together with 15 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, and were organized in topical sections on Michel Raynal and Shmuel Zaks 60th birthday symposium, award nominees, transactional memory, shared memory, distributed and local graph algorithms, modeling issues, game theory, failure detectors, from theory to practice, graph algorithms and routing, consensus and byzantine agreement and radio networks.
Author(s): Lorenzo Alvisi Chair, Rachid Guerraoui, Prasad Jayanti, Idit Keidar, Shay Kutten (auth.), Idit Keidar (eds.)
Series: Lecture Notes in Computer Science 5805 : Theoretical Computer Science and General Issues
Edition: 1
Publisher: Springer-Verlag Berlin Heidelberg
Year: 2009
Language: English
Pages: 532
Tags: Computer Communication Networks; Algorithm Analysis and Problem Complexity; Software Engineering/Programming and Operating Systems; Data Structures; Special Purpose and Application-Based Systems; Performance and Reliability
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 -
