Principles of Distributed Systems
15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011, Proceedings
Published on 9. December 2011
XIII, 564 pages
978-3-642-25873-2 (ISBN)
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.
More details
Other editions
Additional editions
Antonio Fernández Anta | Giuseppe Lipari | Matthieu Roy
Principles of Distributed Systems
15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011, Proceedings
Book
12/2011
Springer
€53.49
Shipment within 7-9 days
Content
- Intro
- Title Page
- Preface
- Organization
- Table of Contents
- From Energy-Efficient Networking to ZEN
- Summary
- References
- Online Regenerator Placement
- Introduction
- Preliminaries
- The Regenerator Location Problem
- Upper Bound for Path Topology
- Upper Bound for General Topologies
- Lower Bound for General Topologies
- Path Maximization in Path Topology. (k=1, d=2)
- Infeasible Instances
- Feasible Instances
- Future Work
- References
- A Quorum-Based Replication Framework for Distributed Software Transactional Memory
- Introduction
- Preliminaries
- System Model
- Motivation: Limitations of SC D-STM Model
- Quorum-Based Replication Data-Flow D-STM Model
- Overview
- Quorum Construction: Flooding Protocol
- Analysis
- Conclusion
- References
- Error-free Multi-valued Broadcast and Byzantine Agreement with Optimal Communication Complexity
- Introduction
- Error-free Communication Optimal A-cast
- Multi-valued A-cast Protocol
- Error-free Communication Optimal ABA
- Multi-valued ABA Protocol
- Error-free Communication Optimal BA and BC
- Open Problems
- References
- Enhancing the Performance of High Availability Lightweight Live Migration
- Introduction
- Related Work
- Design and Implementation
- FGBI
- Block Sharing and Hybrid Compression Support
- Architecture
- FGBI Execution Flow
- Experimental Evaluation
- Experimental Environment
- Downtime Evaluations
- Overhead Evaluations
- Conclusions
- References
- Towards Consistency Oblivious Programming
- Introduction and Related Work
- COP and Acceptability Oriented Programming
- When Can We Use COP
- COP Algorithms
- COP Linked List
- COP Union Find
- COP Red-Black Tree
- Evaluation
- Union Find
- Red Black Tree
- Conclusion
- References
- Regret Freedom Isn't Free
- Introduction
- Model
- Byzantine Regret Freedom in Communication Games
- (k,t)-robustness Is Infeasible in Communication Games
- What If We Know Who Is Byzantine?
- What If We Know How Byzantine Nodes Behave?
- Dealing with Byzantine Failures through Regret Bravery
- Related Work
- Conclusion
- References
- On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming
- Introduction
- Related Work
- Our Contribution
- Definitions and Problem Statement
- Hardness of Approximation
- Approximation Algorithm
- Proper Instances with d=1
- Case d=1
- The General Case
- Open Problems
- References
- On the Cost of Concurrency in Transactional Memory
- Introduction
- Model
- Liveness and Progress
- RAW/AWAR Cost of Permissive STMs
- RAW/AWAR Cost and Protected Data in Progressive STMs
- Constant RAW/AWAR Implementations for Progressive STM
- Protected Data
- Related Work
- Concluding Remarks
- References
- Response Time Bounds for G-EDF without Intra-Task Precedence Constraints
- Introduction
- System Model
- Response Time Characterization
- The Minimum Compliant Vector
- Evaluation
- Conclusion
- References
- Appendix
- Node-Disjoint Multipath Spanners and Their Relationship with Fault-Tolerant Spanners
- Introduction
- Trade-Offs for Non-increasing Graph Metric
- Motivations
- Our Contributions
- Overview
- Main Construction
- Spanners with Few Hops
- Distributed Bounded Hop Spanners
- Fault Tolerant Spanners
- From Fault Tolerant to Multipath Spanner
- Bi-path Spanners
- Construction
- Size Analysis
- Stretch Analysis
- Conclusion
- References
- The First Fully Polynomial Stabilizing Algorithm for BFS Tree Construction
- Introduction
- Model
- Spanning Tree Construction
- Breadth First Search Tree Algorithm
- Question-Answer problem
- Question-Answer Algorithm
- Composition and Complexities
- Conclusion
- References
- Anonymous Agreement: The Janus Algorithm
- Introduction
- System Model
- The JanusIn Roman religion and mythology, Janus is the god of gates. Most often he is depicted as having two heads, facing opposite directions (Wikipedia). The choice of the name is explained by the fact that each process in our algorithm has to look in two directions: forward to check if another process has already started a new round, and back to check if another process concurrently executed the K past rounds. Algorithm
- Description of Janus
- Proof of the Janus Algorithm
- The Case of Homonymous Systems
- Related Work
- Conclusion
- References
- Communication Complexity of Consensus in Anonymous Message Passing Systems
- Introduction
- The Problem and the Model
- Our Results
- Related Work
- Unknown Networks
- Algorithm Flooding-with-Delays
- Known Networks
- Fully Symmetric Networks
- Arbitrary Networks
- Lower Bound
- Do Labels Help?
- Conclusion
- References
- Non-blocking k-ary Search Trees
- Introduction
- k-ary Search Trees
- The Structure
- Modifications to the Tree
- Coordination between Updates
- Helping
- Pseudocode
- Correctness
- Experiments
- Conclusion and Future Work
- References
- Probabilistic Compositional Reasoning for Guaranteeing Fault Tolerance Properties
- Introduction
- Related Work
- Overview
- Prerequisites
- Our Modeling Framework
- Monadic Representation of Probabilistic Systems
- An Example
- Deductive Rules
- Soundness and Semantics of Rules
- Basic Rules
- General Rules Relating Events and Probabilities
- Rules for Normal Distributions
- Case Study
- Conclusion
- References
- Self-stabilizing Mutual Exclusion and Group Mutual Exclusion for Population Protocols with Covering
- Introduction
- Model and Problem Specifications
- Transition System
- The Cover Time Property (Covering)
- Specifications
- Self-stabilizing Phase Clock Tool
- A Self-stabilizing Solution to Mutual Exclusion
- Proving Correctness
- From Mutual Exclusion to Group Mutual Exclusion
- Impossibility Result
- References
- Asynchronous Exclusive Perpetual Grid Exploration without Sense of Direction
- Introduction
- Model and Problem Specification
- Classification of Configurations
- Algorithms for the Perpetual Grid Exploration
- Impossibility Results
- Decomposition in Two Sub-problems
- Grid 33
- Grids 2m with m4
- Grids nm with 3n&m
- Grids nn with n4
- Conclusions and Open Problems
- References
- Fused State Machines for Fault Tolerance in Distributed Systems
- Introduction
- Model
- Background OgaBhar09
- Event-Based Decomposition of Machines
- State-Event Optimized Fusions
- Detection and Correction of Faults
- Detection of Byzantine Faults
- Correction of Faults
- Evaluation
- Experimental Results
- Practical Example: MapReduce
- Conclusion
- References
- Fork-Consistent Constructions from Registers
- Introduction
- System Model
- A Fork-Linearizable Universal Type
- Algorithm Ideas
- Description of Algorithm 1
- Correctness Arguments
- A Weak Fork-Linearizable Shared Memory
- Algorithm Ideas
- Description of Algorithm 2
- Correctness Arguments
- Analysis and Conclusions
- References
- Easy Impossibility Proofs for k-Set Agreement in Message Passing Systems
- Introduction
- System Models and Failure Assumptions
- k-Set Agreement
- Restrictions of Algorithms and Indistinguishability of Runs
- Failure Detectors
- The Impossibility Theorem
- Impossibility in Partially Synchronous and Asynchronous Systems
- Possibility of k-Set Agreement with Initially Dead Processes
- Impossibility with Failure Detector (k,k)
- Discussion
- References
- On the Nature of Progress
- Introduction
- Conventional Explanations
- Modeling Progress
- Minimal and Maximal Progress
- The Scheduler's Role
- The Structure of Progress
- Universal Constructions
- Separation Results
- Partial Methods
- Benevolent Schedulers
- Foundations of Shared-Memory Computability
- Conclusions
- References
- Byzantine Fault-Tolerance with Commutative Commands
- Introduction
- System Model and Definitions
- Recovery Consensus
- Problem Definition
- Solving Recovery Consensus
- BFT Generic Broadcast
- Generic Broadcast
- Solving Generic Broadcast
- State Machine Replication
- A Trivial Algorithm
- An Optimal Algorithm
- Optimizations
- Related Work
- Final Remarks
- References
- Partially Non-Preemptive Dual Priority Multiprocessor Scheduling
- Introduction
- Related Work
- Uniprocessor Scheduling Results
- Multiprocessor Scheduling Results
- Model and Definition
- Partially Non-Preemptive Dual Priority Scheduling Strategy
- Adjusting Task Promotion Times
- Experimental Results
- Conclusion
- References
- Private Similarity Computation in Distributed Systems: From Cryptography to Differential Privacy
- Introduction
- Preliminaries
- Threshold Similarity Protocol
- Differentially Private Similarity Computation
- Differential Privacy
- Differentially Private Similarity
- Utility Analysis
- Conclusion
- References
- The Impact of Edge Deletions on the Number of Errors in Networks
- Introduction
- The Search Problem
- Related Works
- Contribution
- General Results
- Preliminaries
- Relationships between the Number of Liars and the Number of Distance Changes
- Upper Bounds for =1 Deleted Edge in the Random Fault Model
- Lower Bound for = 1 in the Random Fault Model
- Number of Liars after Deletions
- Specific Topologies
- Conclusion
- References
- N-party BAR Transfer
- Introduction
- Related Work
- System Model and Problem Statement
- System Model
- The BAR-Transfer Problem
- BAR-Transfer Algorithm
- Analysis
- Correctness
- Game Theoretic Analysis
- Complexity Analysis
- Conclusions
- References
- Computing with Pavlovian Populations
- Introduction
- Population Protocols
- Game Theory
- From Games to Population Protocols
- Main Result
- Threshold Predicates
- Modulo Counting
- Conclusion
- References
- Asynchronous Rendezvous of Anonymous Agents in Arbitrary Graphs
- Introduction
- Preliminary Notions and Results
- Deterministic Rendezvous
- Randomized Rendezvous
- Conclusion
- References
- Robust Network Supercomputing without Centralized Control
- Introduction
- Model of Computation and Definitions
- Algorithm Description
- Algorithm Analysis
- Tolerating Crash Failures
- Simulation Results
- Conclusion
- References
- On the Power of Waiting When Exploring Public Transportation Systems
- Introduction
- The Problem
- Related Work
- Our Results
- Model and Definitions
- Solvability
- General Case
- Lower Bound on the Number of Moves
- Lower Bound on Time
- Our Algorithm
- Specific Cases
- The Homogeneous Case
- The Highly-Connected Case
- References
- Accurate Byzantine Agreement with Feedback
- Introduction
- Model and Definitions
- The ABA Algorithm
- Accuracy Guarantees of the ABA Algorithm
- Deterministic Accuracy
- Probabilistic Accuracy
- At-Least-One Accuracy
- ABA Algorithm with Weighted Byzantine Agreement
- Experimental Evaluation of ABA Algorithm
- Experimental Setup and Parameters
- Results
- Conclusion and Future Work
- References
- Constructing Mid-Points for Two-Party Asynchronous Protocols
- Introduction
- The crl Process Algebra
- Communication Protocols, Environments, and Mid-Points
- Challenges
- Channels Fidelity
- Non-determinism
- Formal Definitions
- The Framework
- Mid-Point Construction
- State Space Minimization
- The Mid-Point as a State Machine
- TCP Case Study
- Conclusions and Future Work
- References
- Proof of Correctness
- Optimal Instrumentation of Data-flow in Concurrent Data Structures
- Introduction
- Preliminaries
- Concurrent Control-Flow Graphs
- Data-Flow Dependencies in Concurrent Programs
- Observability in Concurrent Programs
- Approach
- Extracting Program Slices
- Building Observability Graph
- SAT-Based Optimization
- Experiments
- Experimental Setup
- Results and Analysis
- Conclusion and Future Work
- References
- Fault-Tolerant Aggregation: Flow-Updating Meets Mass-Distribution
- Introduction
- Preliminaries
- MDFU
- Convergence Time for f=0
- Convergence Time for f&0
- Empirical Evaluation of MDFU
- Convergence Speed against Related Algorithms under No Faults
- Fault Tolerance: Resilience to Message Loss
- MDFU with Linear Prediction
- Continuous Estimation over Time-Varying Input Values
- References
- Provably Good Scheduling of Sporadic Taskswith Resource Sharing on a Two-Type Heterogeneous Multi processor Platform
- Introduction
- System Model and Assumptions
- Overview of Our Approach
- Few Notations and Useful Results
- Notations
- Useful Results
- Creating Virtual Processors on a Two-Type Heterogeneous Multiprocessor Platform
- FF-3C-vpr and Its Speed Competitive Ratio
- The FF-3C-vpr Algorithm
- Time Complexity of FF-3C-vpr
- The Speed Competitive Ratio of FF-3C-vpr Algorithm
- Conclusions
- References
- Appendix
- Algorithm for Creating Virtual Processors
- A Dynamic Elimination-Combining Stack Algorithm
- Introduction
- The Dynamic Elimination-Combining Algorithm
- DECS Performance Evaluation
- The Nonblocking DECS Algorithm
- Discussion
- References
- Author Index
