Principles of Distributed Systems: 13th International Conference, OPODIS 2009, Nîmes, France, December 15-18, 2009. Proceedings

Description

This book constitutes the refereed proceedings of the 13th International Conference on Principles of Distributed Systems, OPODIS 2009, held in Nimes, France, in December 2009. The 23 full papers and 4 short papers presented were carefully reviewed and selected from 72 submissions. The papers are organized in topical sections on distributed scheduling, distributed robotics, fault and failure detection, wireless and social networks, synchronization, storage systems, distributed agreement, and distributed algorithms. Front Matter....Pages - Transactional Memory Today: A Status Report....Pages 1-1 Navigating the Web 2.0 with Gossple ....Pages 2-2 Transactional Scheduling for Read-Dominated Workloads....Pages 3-17 Performance Evaluation of Work Stealing for Streaming Applications....Pages 18-32 Not All Fair Probabilistic Schedulers Are Equivalent....Pages 33-47 Brief Announcement: Relay: A Cache-Coherence Protocol for Distributed Transactional Memory....Pages 48-53 Byzantine Convergence in Robot Networks: The Price of Asynchrony....Pages 54-70 Deaf, Dumb, and Chatting Asynchronous Robots....Pages 71-85 Synchronization Helps Robots to Detect Black Holes in Directed Graphs....Pages 86-98 The Fault Detection Problem....Pages 99-114 The Minimum Information about Failures for Solving Non-local Tasks in Message-Passing Systems....Pages 115-128 Enhanced Fault-Tolerance through Byzantine Failure Detection....Pages 129-143 Decentralized Polling with Respectable Participants....Pages 144-158 Efficient Power Utilization in Multi-radio Wireless Ad Hoc Networks....Pages 159-173 Adversarial Multiple Access Channel with Individual Injection Rates....Pages 174-188 NB-FEB: A Universal Scalable Easy-to-Use Synchronization Primitive for Manycore Architectures....Pages 189-203 Gradient Clock Synchronization Using Reference Broadcasts....Pages 204-218 Brief Announcement: Communication-Efficient Self-stabilizing Protocols for Spanning-Tree Construction....Pages 219-224 On the Impact of Serializing Contention Management on STM Performance....Pages 225-239 On the Efficiency of Atomic Multi-reader, Multi-writer Distributed Memory....Pages 240-254 Abortable Fork-Linearizable Storage....Pages 255-269 On the Computational Power of Shared Objects....Pages 270-284 Weak Synchrony Models and Failure Detectors for Message Passing ( k -)Set Agreement....Pages 285-299 Unifying Byzantine Consensus Algorithms with Weak Interactive Consistency....Pages 300-314 Safe and Eventually Safe: Comparing Self-stabilizing and Non-stabilizing Algorithms on a Common Ground....Pages 315-329 Proactive Fortification of Fault-Tolerant Services....Pages 330-344 Robustness of the Rotor-router Mechanism....Pages 345-358 Brief Annoucement: Analysis of an Optimal Bit Complexity Randomised Distributed Vertex Colouring Algorithm....Pages 359-364 Brief Annoucement: Distributed Swap Edges Computation for Minimum Routing Cost Spanning Trees....Pages 365-371 Back Matter....Pages -