Principles of Distributed Systems: 15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011. Proceedings

Description

This book constitutes the refereed proceedings of the 15th International Conference on Principles of Distributed Systems, OPODIS 2011, held in Toulouse, France, in December 2011. The 26 revised papers presented in this volume were carefully reviewed and selected from 96 submissions. They represent the current state of the art of the research in the field of the design, analysis and development of distributed and real-time systems. Content: Front Matter....Pages - From Energy-Efficient Networking to ZEN....Pages 1-3 Online Regenerator Placement....Pages 4-17 A Quorum-Based Replication Framework for Distributed Software Transactional Memory....Pages 18-33 Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity....Pages 34-49 Enhancing the Performance of High Availability Lightweight Live Migration....Pages 50-64 Towards Consistency Oblivious Programming....Pages 65-79 Regret Freedom Isn’t Free....Pages 80-95 On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming....Pages 96-111 On the Cost of Concurrency in Transactional Memory....Pages 112-127 Response Time Bounds for G-EDF without Intra-Task Precedence Constraints....Pages 128-142 Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners....Pages 143-158 The First Fully Polynomial Stabilizing Algorithm for BFS Tree Construction....Pages 159-174 Anonymous Agreement: The Janus Algorithm....Pages 175-190 Communication Complexity of Consensus in Anonymous Message Passing Systems....Pages 191-206 Non-blocking k-ary Search Trees....Pages 207-221 Probabilistic Compositional Reasoning for Guaranteeing Fault Tolerance Properties....Pages 222-234 Self-stabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering....Pages 235-250 Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction....Pages 251-265 Fused State Machines for Fault Tolerance in Distributed Systems....Pages 266-282 Fork-Consistent Constructions from Registers....Pages 283-298 Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems....Pages 299-312 On the Nature of Progress....Pages 313-328 Byzantine Fault-Tolerance with Commutative Commands....Pages 329-342 Partially Non-Preemptive Dual Priority Multiprocessor Scheduling....Pages 343-356 Private Similarity Computation in Distributed Systems: From Cryptography to Differential Privacy....Pages 357-377 The Impact of Edge Deletions on the Number of Errors in Networks....Pages 378-391 N-party BAR Transfer....Pages 392-408 Computing with Pavlovian Populations....Pages 409-420 Asynchronous Rendezvous of Anonymous Agents in Arbitrary Graphs....Pages 421-434 Robust Network Supercomputing without Centralized Control....Pages 435-450 On the Power of Waiting When Exploring Public Transportation Systems....Pages 451-464 Accurate Byzantine Agreement with Feedback....Pages 465-480 Constructing Mid-Points for Two-Party Asynchronous Protocols....Pages 481-496 Optimal Instrumentation of Data-flow in Concurrent Data Structures....Pages 497-512 Fault-Tolerant Aggregation: Flow-Updating Meets Mass-Distribution....Pages 513-527 Provably Good Scheduling of Sporadic Tasks with Resource Sharing on a Two-Type Heterogeneous Multiprocessor Platform....Pages 528-543 A Dynamic Elimination-Combining Stack Algorithm....Pages 544-561 Back Matter....Pages -