Principles of Distributed Systems

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.

Table of Contents

Chapter 1 Transactional Memory Today: A Status Report
Chapter 2 Navigating the Web 2.0 with GOSSPLE
Chapter 3 Transactional Scheduling for Read-Dominated Workloads
Chapter 4 Performance Evaluation of Work Stealing for Streaming Applications
Chapter 5 Not All Fair Probabilistic Schedulers Are Equivalent
Chapter 6 Brief Announcement: Relay: A Cache-Coherence Protocol for Distributed Transactional Memory
Chapter 7 Byzantine Convergence in Robot Networks: The Price of Asynchrony
Chapter 8 Deaf, Dumb, and Chatting Asynchronous Robots
Chapter 9 Synchronization Helps Robots to Detect Black Holes in Directed Graphs
Chapter 10 The Fault Detection Problem
Chapter 11 The Minimum Information about Failures for Solving Non-local Tasks in Message-Passing Systems
Chapter 12 Enhanced Fault-Tolerance through Byzantine Failure Detection
Chapter 13 Decentralized Polling with Respectable Participants
Chapter 14 Efficient Power Utilization in Multi-radio Wireless Ad Hoc Networks
Chapter 15 Adversarial Multiple Access Channel with Individual Injection Rates
Chapter 16 NB-FEB: A Universal Scalable Easy-to-Use Synchronization Primitive for Manycore Architectures
Chapter 17 Gradient Clock Synchronization Using Reference Broadcasts
Chapter 18 Brief Announcement: Communication-Efficient Self-stabilizing Protocols for Spanning-Tree Construction
Chapter 19 On the Impact of Serializing Contention Management on STM Performance
Chapter 20 On the Efficiency of Atomic Multi-reader, Multi-writer Distributed Memory
Chapter 21 Abortable Fork-Linearizable Storage
Chapter 22 On the Computational Power of Shared Objects
Chapter 23 Weak Synchrony Models and Failure Detectors for Message Passing ($k$-)Set Agreement
Chapter 24 Unifying Byzantine Consensus Algorithms with Weak Interactive Consistency
Chapter 25 Safe and Eventually Safe: Comparing Self-stabilizing and Non-stabilizing Algorithms on a Common Ground
Chapter 26 Proactive Fortification of Fault-Tolerant Services
Chapter 27 Robustness of the Rotor-router Mechanism
Chapter 28 Brief Annoucement: Analysis of an Optimal Bit Complexity Randomised Distributed Vertex Colouring Algorithm
Chapter 29 Brief Annoucement: Distributed Swap Edges Computation for Minimum Routing Cost Spanning Trees