Principles of Distributed Systems

This book constitutes the refereed post-proceedings of the 9th International Conference on Principles of Distributed Systems, OPODIS 2005, held in Pisa, Italy in December 2005. The volume presents 30 revised full papers and abstracts of 2 invited talks. The papers are organized in topical sections on nonblocking synchronization, fault-tolerant broadcast and consensus, self-stabilizing systems, peer-to-peer systems and collaborative environments, sensor networks and mobile computing, security and verification, real-time systems, and peer-to-peer systems.

Invited Talk 1. - Distributed Algorithms for Systems of Autonomous Mobile Robots. - Invited Talk 2. - Real-Time Issues in Mobile Wireless Networks. - Session 1: Nonblocking Synchronization. - A Lazy Concurrent List-Based Set Algorithm. - Efficiently Implementing a Large Number of LL/SC Objects. - Can Memory Be Used Adaptively by Uniform Algorithms? . - Randomized Wait-Free Consensus Using an Atomicity Assumption. - Session 2: Fault-Tolerant Broadcast and Consensus. - Optimal Randomized Fair Exchange with Secret Shared Coins. - Two Abstractions for Implementing Atomic Objects in Dynamic Systems. - Parsimonious Asynchronous Byzantine-Fault-Tolerant Atomic Broadcast. - Session 3: Self-stabilizing Systems. - Self-stabilizing Population Protocols. - A Self-stabilizing Link-Coloring Protocol Resilient to Unbounded Byzantine Faults in Arbitrary Networks. - Timed Virtual Stationary Automata for Mobile Networks. - Asynchronous and Fully Self-stabilizing Time-Adaptive Majority Consensus. - Session 4: Peer-to-Peer Systems and Collaborative Environments. - Stable Predicate Detection in Dynamic Systems. - MTcast: Robust and Efficient P2P-Based Video Delivery for Heterogeneous Users. - Towards a Theory of Self-organization. - Node Discovery in Networks. - Session 5: Sensor Networks and Mobile Computing. - Optimal Clock Synchronization Under Energy Constraints in Wireless Ad-Hoc Networks. - Half-Space Proximal: A New Local Test for Extracting a Bounded Dilation Spanner of a Unit Disk Graph. - A State-Based Model of Sensor Protocols. - Session 6: Security and Verification. - Approximation Bounds for Black Hole Search Problems. - Revising UNITY Programs: Possibilities and Limitations. - Session 7: Real-Time Systems. - The Partitioned, Static-Priority Scheduling of Sporadic Real-Time Tasks with Constrained Deadlines onMultiprocessor Platforms. - New Schedulability Tests for Real-Time Task Sets Scheduled by Deadline Monotonic on Multiprocessors. - Static-Priority Scheduling of Sporadic Messages on a Wireless Channel. - Implementing Reliable Distributed Real-Time Systems with the ? -Model. - Session 8: Peer-to-Peer Systems. - Reconfigurable Distributed Storage for Dynamic Networks. - Skip B-Trees. - Bounding Communication Cost in Dynamic Load Balancing of Distributed Hash Tables. - Session 9: Sensor Networks and Mobile Computing. - On the Power of Anonymous One-Way Communication. - Quality-Aware Resource Management for Wireless Sensor Networks. - Topology Control with Limited Geometric Information.