Principles of Distributed Systems: 11th International Conference, OPODIS 2007, Guadeloupe, French West Indies, December 17-20, 2007, Proceedings (Lecture Notes in Computer Science, 4878)

This book constitutes the refereed proceedings of the 11th International Conference on Principles of Distributed Systems, OPODIS 2007, held in Guadeloupe, French West Indies, in December 2007. The 32 revised full papers presented were carefully reviewed and selected from 106 submissions. The papers address all current issues in theory, specification, design and implementation of distributed and embedded systems. A broad range of topics are addressed. Title Page Preface Organization Table of Contents A Decentralized, Scalable, and Autonomous Grid Monitoring System Introduction Grid Monitoring Systems Network Weather Service (NWS) Globus Monitoring and Discovery System (MDS) Relational Grid Monitoring Architecture (R-GMA) Ganglia The Grid Monitoring Architecture Decentralized and Scalable Communication Scheme A Peer-to-Peer Architecture A Directed Gossip Protocol An Autonomous Monitoring System Experimentations Implementation Details Performance Measures and Optimization Conclusion and Perspectives A Formal Analysis of the Deferred Update Technique Introduction A General Serializable Database The Deferred Update Technique Preliminaries Abstract Algorithm Termination Protocol Conclusion ASAP: A Camera Sensor Network for Situation Awareness Introduction Understanding ASAP Requirements Example Application: Video Based Surveillance Application Requirements Architecture Sensor Agent ASAP Agent Implementation Sensor Agent ASAP Agent Evaluation Experimental Setup Scalability, Query Handling, and Latency Network Bandwidth Other Results Related Works Conclusions Asynchronous Active Recommendation Systems Introduction Preliminaries Building Block: Algorithm select Randomized Multiplexing Exact Preference Reconstruction The Algorithm Analysis Approximate Preference Reconstruction Algorithm Brute-Force Determination of Multiprocessor Schedulability for Sets of Sporadic Hard-Deadline Tasks Introduction Sporadic Task Scheduling The Abstract State Model Clock-Tick Transitions Ready Transitions Specific Scheduling Policies Generic Algorithm Computational Complexity Performance Conclusion Byzantine Consensus with Few Synchronous Links Introduction Computation Model and the Consensus Problem Computation Model The Consensus Problem The Byzantine Protocol Correctness of the Protocol Discussion On the Efficiency of the Protocol On the Minimality of the 2t-bisource Conclusion Clock Synchronization in the Byzantine-Recovery Failure Model Introduction System Model and Problem Statement The Algorithm Properties of the Algorithm Initialization Related work Computing Without Communicating: Ring Exploration by Asynchronous Oblivious Robots Introduction Framework Our Results Related Work Preliminaries Terminology and Definitions Basic Restriction Exploration of a Ring Overview of the Algorithm Set-Up Phase Tower-Creation Phase Exploration Phase Size of the Minimum Team Conclusion Deterministic Communication in the Weak Sensor Model Introduction Oblivious Protocols Message-Complexity Lower Bound A Message-Complexity-Optimal Protocol: Primed Selection Delay Lower Bounds A Delay-Optimal Equiperiodic Protocol for kn1/6loglogn Adaptive Protocols: Reduced Primed Selection Deterministic Leader Election in Anonymous SensorNetworks Without Common Coordinated System Introduction Preliminaries Model Words and Lyndon Words Leader Election Leader Election with Chirality Leader Election Without Chirality Conclusion Distance Sensitive Snapshots in Wireless Sensor Networks Introduction Model and Specification Distance Sensitive Latency Snapshots Distance Sensitive Resolution Snapshots Distance Sensitive Rate Snapshots Distance Sensitive Rate by Data Division Distance Sensitive Rate by Time Division Irregular Networks Related Work Conclusion Distributed Approximation Algorithms for Finding 2-Edge-Connected Subgraphs Introduction Contributions Further Related Work Model Outline and Definitions The Unweighted Case The Weighted Case The Chain Case The General Case Conclusion Does Clock Precision Influence ZigBee’s Energy Consumptions? Introduction ZigBee and IEEE 802.15.4 MODEST and Supporting Tools Modelling Models Energy Consumption Clock Precision Simulations Conclusion From an Intermittent Rotating Star to a Leader Introduction Leader Oracle: Motivation Existing Approaches to Implement Content of the Paper: Towards Weaker and Weaker Synchrony Assumptions Definitions Basic Distributed System Model The Oracle Class The Additional Assumption A An A+-Based Leader Algorithm Principles and Description of the Algorithm Proof of the Algorithm An A-Based Leader Algorithm From A+ to A Proof of the Algorithm A Bounded Variable A-Based Leader Algorithm Bounding all the Variables susp_leveli[k] Proof and Properties of the Algorithm Conclusion Global Deadline-Monotonic Scheduling ofArbitrary-Deadline Sporadic Task Systems Introduction Model and Definitions Task Model Processor Model Deadline Monotonic Scheduling Processor Speedup Bounds Related Work A dm Schedulability Test A Processor Speedup Bound Conclusions LFTHREADS: A Lock-Free Thread Library Introduction Preliminaries Detailed Description of the LFthreads Library Data Structures and Fundamental Operations Thread Operations in LFthreads Blocking Thread Synchronization and the RHO Method Correctness of the Synchronization in LFthreads Experimental Study Conclusion Making Distributed Applications Robust Introduction Background System Model The ARcast Mechanism ARcast Definition ARcast Implementation The OARcast Mechanism OARcast Definition OARcast Implementation The Translation Mechanism Definition Implementation Illustration: BFT Conclusion Correctness of OARcast Correctness of Translation Maximizing the Number of Broadcast Operations inStatic Random Geometric Ad-Hoc Networks Introduction Preliminaries The Upper Bound The Algorithm The Distributed Version Open Problems N-Consensus is the Second Strongest Objectfor N + 1 Processes Introduction Preliminaries Inseparability Inseparably Connected Sets of States Non-separating Paths P-reconciliation Protocol Emulation Overview Correctness Multiple Initial States Conclusion Non-Searchability of Random Power-Law Graphs Introduction Related Works Our Contribution Models Graph Models: The Chung-Lu Model Graph Models: The Móri Model Modeling the Searching Process Vertex Equivalence The Chung-Lu Graph The Móri Graph Conditional Equivalence in the Móri Tree Proof of Theorem 2 Conclusion and Open Problems O(log n)-Time Overlay Network Constructionfrom Graphs with Out-Degree 1 Introduction Other Related Work Model Double-Headed Radix Trees Algorithms Pre-stage Merging Stage Fault Tolerance Issues Extension to an Asynchronous Model Conclusion Appendix Analysis of Time Complexity Merging Two DHR Trees On the Self-stabilization of Mobile Robots in Graphs Introduction Model Impossibility Results Self-stabilizing Deterministic Naming in Acyclic Networks with Half-Duplex Links Probabilistic Naming in Arbitrary Networks Naming and Leader Election From Naming to Leader Election From Leader Election to Naming Concluding Remarks Peer to Peer Multidimensional Overlays:Approximating Complex Structures Introduction Design Rationale Approximation Through Gossip Small-World Networks Gossip-Based Overlay Construction Approximating the Close Neighbourhood: Coverage and Closeness Protocol Details View Evolution Using Voronoï Cell Size Estimation Discovery of a New Configuration: Naive Approach Discovery of a New Configuration: Efficient, Linear Time Approach Experimental Evaluation Related Works Conclusion Secretive Birds:Privacy in Population Protocols Introduction Private Population Protocols Computing Predicates Privately Computing Remainder Predicates Computing Threshold Predicates Computing All Semilinear Predicates Concluding Remarks Self-stabilizing and Byzantine-TolerantOverlay Network Introduction Related Work The Model The BSS Overlay Service Specification Data Structures The Sequence of Subgraphs The Views The Epoch and Epoch List The Dissemination Structure Membership Maintenance Recovery of Members Epoch Renewal and Epoch List Stabilization Periodical Epoch Update Stabilization of the Overlay Network Structures Conclusion Separability to Help Parallel Simulationof Distributed Computations Introduction Separability in Distributed Computations Context of the Study Distributed Computation Model Separability Criterion Distributed Computation Model for Parallel Simulation Scheduling of a Parallel Simulation Parallel Simulation Using Delays An Example of Separability Analysis Slicing in the General Case Performance Conclusion Parallel Simulation Using Frequencies Principle Jitter Algorithm Example Conclusion Small-World Networks:From Theoretical Bounds to Practical Systems Introduction System Model and Simulation Setup Neighbor Selection Simulation Setup Routing Analysis in Small-World Overlay Networks Small-Worlds with Randomly Selected Shortcuts Small-Worlds with Shortcuts According to Kleinberg's Distribution Kleinberg-Like Epidemic-Based Small-World Networks Conclusion The Anonymous Consensus Hierarchyand Naming Problems Introduction Preliminaries Anonymous Consensus Numbers Naming Strong Naming Summary Deterministic Types The Baskets Queue Introduction The Baskets Queue Performance The Baskets Queue Data Structures The Baskets Queue Operations Performance The Benchmarked Algorithms The Benchmarks The Experiments Empirical Results Memory Management The Tagging Mechanism and the ABA Problem Correctness Proof Linearizability of Our Algorithm The Cost of Monotonicity in Distributed Graph Searching Introduction Model and Definitions Our Results Related Work Lower Bound Upper Bound Idea of Protocol mc_search Protocol mc_search Correctness of Protocol mc_search Timed Quorum Systems forLarge-Scale and Dynamic Environments Introduction System Model and Problem Definition Model Problem Preliminary Notations and Definitions Probabilistic Atomic Object Timed Quorum System Timed Quorum System Implementation for Probabilistic Atomic Memory Replicating During Client Operations Quorum Probe Contacting Participants Randomly Correctness Proof and Performance Analysis Assumptions and Notations Correctness Proof Performance Analysis Conclusion Worm Versus Alert:WhoWins in a Battle for Control ofa Large-Scale Network? Introduction Our Model Results Other Related Work Alert Versus Worm in an Expanding Overlay Network Phase I Analysis of Phase II Analysis of Phase III Empirical Results Is Expansion Necessary? Conclusion and Future Work Author Index Annotation This book constitutes the refereed proceedings of the 11th International Conference on Principles of Distributed Systems, OPODIS 2007, held in Guadeloupe, French West Indies, in December 2007. The 32 revised full papers presented were carefully reviewed and selected from 106 submissions. The papers address all current issues in theory, specification, design and implementation of distributed and embedded systems. Topics addressed are 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 robot, mobile computing and networks, peer- to-peer systems, overlay networks, complexity and lower bounds, performance analysis of distributed systems, realtime systems, security issues in distributed computing and systems, sensor networks: theory and practice, specification and verification of distributed systems, as well as testing and experimentation with distributed systems