Principles of Distributed Systems

Name: Principles of Distributed Systems | 15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011, Proceedings
Brand: Springer
Price: 53.49 EUR
Availability: OnlineOnly

15th International Conference, OPODIS 2011, Toulouse, France, December 13-16, 2011, Proceedings

Antonio Fernández Anta Giuseppe Lipari Matthieu Roy(Herausgeber*in)

Springer (Verlag)

Erschienen am 9. Dezember 2011

XIII, 564 Seiten

E-Book

PDF mit Wasserzeichen-DRM

Systemvoraussetzungen

978-3-642-25873-2 (ISBN)

53,49 €inkl. 7% MwSt.

Systemvoraussetzungen

für PDF mit Wasserzeichen-DRM

E-Book Einzellizenz

Als Download verfügbar

Beschreibung

Weitere Details

Weitere Ausgaben

Inhalt

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

Systemvoraussetzungen

Als PDF speichern Als Link merken