Principles Of Distributed Systems: 14th International Conference, Opodis 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings (lecture Notes In Computer Science)

This book constitutes the refereed proceedings of the 14th International Conference on Principles of Distributed Systems, OPODIS 2010, held in Tozeur, Tunisia, in December 2010. The 32 full papers and 4 brief announcements presented were carefully reviewed and selected from 122 submissions. The papers are organized in topical sections on robots; randomization in distributed algorithms; brief announcements; graph algorithms; fault-tolerance; distributed programming; real-time; shared memory; and concurrency. Title Preface Organization Table of Contents Robots Pattern Formation through Optimum Matching by Oblivious CORDA Robots Introduction Preliminary Model Algorithm — CWM-Form Terminology Clockwise Matching Graph $G(A,B)$ Definition of CWM Properties of CWM Proof of Theorem 1 Conclusion RoboCast: Asynchronous Communication in Robot Networks Introduction Model Local Coordinate System RoboCast Line RoboCast Line RoboCast: A Composable Version RoboCast of the Local Coordinate System Motion Complexity Analysis Collision-Free RoboCast RoboCast Applications Asynchronous Deterministic 2-Gathering Asynchronous Stigmergy Conclusion and Perspectives Randomization in Distributed Algorithms Biased Selection for Building Small-World Networks Introduction Related Work Contributions Structure of the Rest of the Paper Definitions and Experimental Setup Definitions Experimental Setup Biased Selection The Biased Selection Algorithm Correctness Convergence Rate Experimental Results Accuracy of Biased Selection Building Small-World Networks with Biased Selection Building Incomplete Small-World Networks with Biased Selection Conclusions and Future Work Application of Random Walks to Decentralized Recommender Systems Introduction Preliminaries Collaborative Filtering Epidemic Protocols Related Work Decentralization of CF Algorithms Decentralized Prediction through Random Walk Experiments and Results Evaluation Methodology and Results Analysis of the Behavior of Random Walk Conclusion Uniform and Ergodic Sampling in Unstructured Peer-to-Peer Systems with Malicious Nodes Introduction System Model Adversary Security Mechanisms Uniform and Ergodic Sampling Assumptions and Terminology Sampling Properties Related Work Characterization of the Uniform and Ergodic Sampling Problem Conclusion Brief Announcements I Self-stabilizing (k,r)-Clustering in Wireless Ad-hoc Networks with Multiple Paths Introduction Our Contribution System Settings Self-Stabilizing Algorithm for $(k,r)$-Clustering Discussion and Conclusions Self-stabilizing Byzantine Asynchronous UnisonA full version of this work is available in 敳敲癥搠䁤 㴀 ⨀੯扲敡歳灡捥−紀⸀Ⰰ吀栀椀猀 眀漀爀欀 眀愀猀 昀甀渀搀攀搀 椀渀 瀀愀爀琀 戀礀 䄀一刀 瀀爀漀樀攀挀琀猀 匀䠀䄀䴀䄀一Ⰰ 䄀䰀䄀䐀䐀䤀一Ⰰ 愀渀搀 匀倀䄀䐀䔀匀 Graph Algorithms Reliably Detecting Connectivity Using Local Graph Traits Introduction Model The Impossibility of Locally Characterizing Connectivity Local Graph Traits That Imply $k$-Connectivity A Natural Local Trait for $k$-Connectivity Small Edges Increase Connectivity Spanning Trees with Small Edges Imply $k$-Connectivity Applying Local Graph Traits to Distributed Algorithms Testing for k-Connectivity Maintaining k-Connectivity of Robot Swarms Distributed Game-Theoretic Vertex Coloring Introduction Background Distributed Vertex Coloring as a Game Simultaneous Execution of Selfish Steps Distributing Global Information Self-stabilization Algorithm Engineering Implementation Details Performance Evaluation: Simulations Performance Evaluation: Experiments Constructing a Map of an Anonymous Graph: Applications of Universal Sequences Introduction Model, Definitions and Known Results Our Model Universal Exploration Sequences The Map Construction Problem Map Construction with Knowledge of Upper Bound Using a UXS as a Sequence for Graph Identification An Algorithm with Efficient Identification of Nodes Universal Algorithms for Map Construction Guessing the Value of $n$ More Efficient Map Construction Solving Rendezvous Brief Announcements II Effect of Fairness in Model Checking of Self-stabilizing Programs Motivation Current Results Case Study: Dijkstra's K-State Program Other Results Conclusion A Formal Framework for Conformance Testing of Distributed Real-Time Systems Introduction Modelling Distributed Systems Using Timed Automata Testing Architecture Test Generation Principle Conclusion and Future Work Fault-Tolerance Signature-Free Broadcast-Based Intrusion Tolerance: Never Decide a Byzantine Value Introduction Computation System Model Base Model Asynchronous Communication Network An Implementation of the Validated Broadcast Abstraction Intrusion-Tolerant Byzantine Consensus and the Enriched Model Byzantine Consensus Enriched Model for Multivalued ITB Consensus Generic Consensus Based on the WB or NDB Abstraction Consensus Based on the Validated Broadcast Abstraction Discussion A Randomized VB-Based Byzantine Binary Consensus Algorithm Conclusion A Fault Avoidance Strategy Improving the Reliability of the EGI Production Grid Infrastructure Introduction The EGI Grid: Technology Backgrounds Improving Grid Reliability through Fault Avoidance Introducing Fault-Avoidance in the EGI Production Infrastructure Performance Evaluation and Results Analysis Studying the Impact of Fault Avoidance for MPI Job Submission Test Related Work and Discussion Conclusions Failure Detectors Encapsulate Fairness Introduction Related Work Definitions Asynchronous System Model Failure Detectors Fairness Constraints Fairness-Based Partially-Synchronous System Models Methodology Extracting Fairness Interface between Scheduler and Application Algorithm Description Extracting Chandra-Toueg Failure Detectors from Fairness-Based Systems Discussion $(\amga[x]\times\sgma[z])$-Based $k$-Set Agreement Algorithms Introduction System Model and Failures Detectors $\sgma[z]$ and $k$-Set-Agreement The $\mathsf{Alpha}_k$ Abstraction Implementing $\mathsf{Alpha}_k$ with \sgma[k] Proof A $k$-Set Agreement Algorithm Solving $k$-Set Agreement with $\amga[x]$ and $\sgma[z]$ An Impossibility Result Concluding Remarks Distributed Programming Distributed Programming with Tasks Introduction Model Basic Protocol: Equivalence of Snapshots Model and IS Model Extended Protocol for 01-Exclusion Tasks Conclusion SkewCCC+: A Heterogeneous Distributed Hash Table Introduction Our Contribution Related Work Organization Construction Partitioning Tree Virtual Connections SkewCCC+ Algorithms Searching Joining and Leaving Rebalancing Analysis The Adversary Imbalance in a Correct Stable State Correctness and Cost of Balancing Amortizing the Cost of Balancing Detecting Imbalance The Cost of Routing Storing Data Conclusion On the Automated Implementation of Time-Based Paxos Using the IOA Compiler Introduction Background I/O Automata and the GTA Models The IOA Language and the IOA Compiler The Paxos Algorithm Implementation of the Paxos Algorithm Extending the IOA Compiler Procedure Experimentation Conclusions Real-Time Partitioning Real-Time Systems on Multiprocessors with Shared Resources Introduction Contributions Related Work Task and Platform Model The Blocking Aware Partitioning Algorithms Blocking-Aware Partitioning Algorithm (BPA) Synchronization-Aware Partitioning Algorithm (SPA) Experimental Evaluation and Comparison of Algorithms Experiment Setup Results Conclusion On Best-Effort Utility Accrual Real-Time Scheduling on Multiprocessors Introduction Models and Objective GUA Class of Algorithms Basic Rationale Overview Non-Greedy Global Utility Accrual (NG-GUA) Greedy Global Utility Accrual (G-GUA) Algorithm Properties Experimental Evaluation ChronOS Real-Time Linux Experimental Setup Results without Dependencies Results with Dependencies Scheduling Overheads Conclusions Tardiness Bounds for Global EDF with Deadlines Different from Periods Introduction A Characterization of Tardiness The Minimum Compliant Vector Existence and Uniqueness Improved Computation Algorithm Conclusion Shared Memory Cache-Aware Lock-Free Queues for Multiple Producers/Consumers and Weak Memory Consistency Introduction Related Work The New Algorithm Correctness and Analysis Properties of an Array Block Properties of the Chain of Array Blocks Linearizability Lock-Freedom Concurrent FIFO Queue Experiments Conclusions An Adaptive Technique for Constructing Robust and High-Throughput Shared Objects Introduction Related Work Model Prior Art Combining Techniques Combining Tree GVW-efficient-synch-prim Bounded Wait Combining HK07 Difficulties in Adapting to the Unknown Asynchrony Bound E The New Algorithm High Level Overview A More Detailed Description of the Algorithm Communal Procedures Algorithm Analysis Outline Conclusions Efficient Lock Free Privatization Introduction and Related Work PG in a Nutshell PG Privatization Algorithm Overview of PG and LFRC PG and LFRC Usage for Reclamation Evaluation Conclusion A Competitive Analysis for Balanced Transactional Memory Workloads Introduction Contributions Related Work Model and Definitions Clairvoyant Algorithm Analysis of Clairvoyant Algorithm Non-clairvoyant Algorithm Analysis of Non-clairvoyant Algorithm Hardness of Balanced Transaction Scheduling Conclusions Concurrency Fast Local-Spin Abortable Mutual Exclusion with Bounded Space Introduction Preliminaries S-HAD and Abortable Mutual Exclusion A Simple Implementation of S-HAD An Implementation of S-HAD with Bounded Space Conclusions Turning Adversaries into Friends: Simplified, Made Constructive, and Extended Introduction Model Set Consensus Power of A Characterizing Colorless Tasks Extension to Other Models Concluding Remarks Quasi-Linearizability: Relaxed Consistency for Improved Concurrency Introduction Other Relaxed Consistency Conditions Quasi Linearizable, Definition Lineariazablity Review Random Dequeued Queue Segmented Queue Segmented Stack Performance Evaluation Bitonic[W] Counting Network Conclusions A Token-Based Distributed Algorithm for the Generalized Resource Allocation Problem Introduction Related Works Preliminary The Computational Model The Generalized Resource Allocation Problem Coterie Performance Measures The Proposed Algorithm Local Variables at Each Process Structure of the Token Object Description of the Proposed Algorithm Proof of Correctness and Performance Analysis Conclusion On the Message Complexity of Global Computations Introduction Lower Bounds Our Results Paper Organization Model and Strategy Network Model Adversary Model Complexity Lower Bound in General Networks Not-Dense Network Dense Network Extremely Dense Network Tightness Complexity Lower Bound in Regular Networks Regular Typical Networks Regular Dense Network Conclusions Optimizing Regenerator Cost in Traffic Grooming Introduction Related Work Our Contribution Preliminaries Definitions and Problem Statement Lower Bounds Path and Ring Networks Tree Networks $G, \pp, \infty$ Instances An Approximation Algorithm Scheme for Any Graph G and Any Value of $g$ The Approximation Algorithm for Tree Networks Beyond Tree Networks: A Matching Technique The Endpoint Intersection Graph Algorithm for General Networks Conclusion and Future Work On Minimizing Average End-to-End Delay in P2P Live Streaming Systems Introduction Related Work Problem Formulation Preliminaries and Modeling MADPS Problem Approximation Algorithm Overview of Techniques Formulation about Primal and Dual Approximation Algorithm Algorithm Analysis Running Time Conclusion Monotonic Stabilization Introduction Preliminaries Optimal Monotonic Convergence Monotonic Convergence Concluding Remarks Upper and Lower Bounds of Space Complexity of Self-Stabilizing Leader Election in Mediated Population Protocol Introduction Model Description — SS-LE MPP Simple SS-LE MPP with $n$-1 Agent-States SS-LE MPP with (2/3)$n$ Agent-States for $n$ Agents Lower Bounds for SS-LE MPP Conclusion Improving Space Complexity of Self-stabilizing Counting on Mobile Sensor Networks Introduction Preliminaries System Model Execution Fairness Complexity Measure Self-stabilizing Counting Problem A self-stabilizing Counting Protocol Using 2P States Protocol Correctness Convergence Time A self-stabilizing Counting Protocol Using $3P/2$ States Protocol Correctness Concluding Remarks Author Index The 14th International Conference On Principles Of Distributed Systems (opodis 2010) Took Place During December 14–17, 2010 In Tozeur, Tunisia. It Continued A Tradition Of Successful Conferences; Chantilly (1997), Amiens (1998), Hanoi (1999), Paris (2000), Mexico (2001), Reims (2002), La Martinique (2003), Gre- Ble (2004), Pisa (2005), Bordeaux (2006), Guadeloupe (2007), Luxor (2008) And Nˆ?mes (2009). The Opodis Conference Constitutes An Open Forum For The Exchange Of Sta- Of-the-art Knowledge On Distributed Computing And Systems Among Researchers From Around The World. Following The Tradition Of The Previous Events, The P- Gram Was Composed Of High-quality Contributed Papers. The Program Call For Papers Looked For Original And Signi?cant Research Contributions To The Theory, Speci?cation, Design And Implementation Of Distributed Systems, Including: – Communication And Synchronization Protocols – Distributed Algorithms, Multiprocessor Algorithms – Distributed Cooperative Computing – Embedded Systems – Fault-tolerance, Reliability, Availability – Grid And Cluster Computing – Location- And Context-aware Systems – Mobile Agents And Autonomous Robots – Mobile Computing And Networks – Peer-to-peer Systems, Overlay Networks – Complexity And Lower Bounds – Performance Analysis Of Distributed Systems – Real-time Systems – Security Issues In Distributed Computing And Systems – Sensor Networks: Theory And Practice – Speci?cation And Veri?cation Of Distributed Systems – Testing And Experimentation With Distributed Systems In Response To This Call For Papers, 122 Papers Were Submitted. Each Paper Was Reviewed By At Least Three Reviewers, And Judged According To Scienti?c And P- Sentation Quality, Originality And Relevance To The Conference Topics. This book constitutes the refereed proceedings of the 17th International Conference on Principles of Distributed Systems, OPODIS 2013, held in Nice, France, in December 2013. Papers were sought soliciting original research contributions to the theory, specification, design and implementation of distributed systems. Annotation Constituting the refereed proceedings of the 14th International Conference on Principles of Distributed Systems, OPODIS 2010, held in Tozeur, Tunisia, in December 2010, this volume contains 32 full papers on topics discussed at the conference