Distributed Computing
25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011, Proceedings
Published on 20. October 2011
XVII, 506 pages
978-3-642-24100-0 (ISBN)
Description
This book constitutes the refereed proceedings of the 25th International Symposium on Distributed Computing, DISC 2011, held in Rome, Italy, in September 2011.
The 31 revised full papers presented together with invited lectures and brief announcements were carefully reviewed and selected from 136 submissions. The papers are organized in topical sections on distributed graph algorithms; shared memory; brief announcements; fault-tolerance and security; paxos plus; wireless; network algorithms; aspects of locality; consensus; concurrency.
More details
Other editions
Additional editions
David Peleg
Distributed Computing
25th International Symposium, DISC 2011, Rome, Italy, September 20-22, 2011, Proceedings
Book
09/2011
1st Edition
Springer
€53.49
Shipment within 7-9 days
Content
- Title
- Preface
- Symposium Organization
- Table of Contents
- Invited Lecture & Best Student Paper: Rendezvous (Session 1a)
- DISC 2011 Invited Lecture: Deterministic Rendezvous in Networks: Survey of Models and Results
- Introduction
- Taxonomy of Rendezvous Problems
- Synchronous Rendezvous
- Asynchronous Rendezvous
- References
- Fast and Scalable Rendezvousing
- Introduction
- Preliminaries
- Related Work
- Algorithm Description
- Nonadaptive Algorithm
- Adding Adaptivity
- Pragmatic Extensions and Considerations
- Correctness
- Evaluation
- Synchronous Queues
- Concurrent Stack
- Conclusion
- References
- Distributed Graph Algorithms (Session 1b)
- Beeping a Maximal Independent Set
- Introduction
- Related Work
- Model
- Lower Bound for Uniform Algorithms
- Using an Upper Bound on n
- Wake-on-Beep and Sender Collision Detection
- Wake-on-Beep with No Collision Detection
- Synchronized Clocks
- References
- Trading Bit, Message, and Time Complexity of Distributed Algorithms
- Introduction
- Related Work
- Model and Definitions
- Tight Bounds on the Transmittable Information
- Lower Bound on the Time Complexity Depending on the Bit (and Message) Complexity
- Algorithms Trading among Bit, Message, and Time Complexity
- Coloring Algorithm
- Randomized O(+ log$^1+1/log* n$ n) Coloring
- Rand. O(?) Coloring in Time t$^c$ using O(logn/logt) Bits
- Deterministic ?+1 Coloring
- MIS Algorithm
- References
- Combinatorial Algorithms for Distributed Graph Coloring
- Introduction
- Algebraic versus Combinatorial Algorithms
- Distributed Coloring
- Our Techniques
- Related Work
- Preliminaries
- Definitions and Notation
- Coloring Procedures
- The Generic Method
- Coloring Algorithms
- Procedure Simple-Col
- Procedures Poly-Col and Fast-Col
- References
- Physical Expander in Virtual Tree Overlay
- Introduction
- Related Works
- The Expander Property of G
- Notations
- Preliminary Results
- Main Result
- Distributed Construction of G
- Computational Model
- Uniformly-Random Matching Construction
- Experimental Evaluation in Dynamic Environment
- Concluding Remarks
- References
- Shared Memory (Session 1c)
- Sub-logarithmic Test-and-Set against a Weak Adversary
- Introduction
- Related Work
- Preliminaries
- Test-and-Set Algorithm
- Description
- Proof of Correctness
- Proof of Performance
- Multi-use Test-and-Set
- Lower Bound
- Summary and Future Work
- References
- Tight Space Bounds for l-Exclusion
- Introduction
- Motivation
- The -Exclusion Problem
- Results
- Related Work
- A Space Lower Bound
- The Model
- Changing the Value of a Bit
- Locking
- Locking and Values
- Flexibility
- Main Lemma and Proof of Theorem 2
- A Space Upper Bound: The Two-bits Algorithm
- Weak l-Exclusion
- Discussion
- References
- SMV: Selective Multi-Versioning STM
- Introduction
- Related Work
- Exponential Memory Growth
- SMV Algorithm
- Overview of Data Structures
- Basic Algorithm
- Allowing Concurrent Access to the Time Points List
- Implementation and Evaluation
- Compared Algorithms
- Experiment Setup
- Performance Measurements
- Latency and Predictability of Long Read-Only Operations
- Memory Demands
- Conclusions
- References
- Brief Announcements I (Session 1d)
- Brief Announcement: Leaderless Byzantine Paxos
- References
- Brief Announcement: When You Don't Trust Clients: Byzantine Proposer Fast Paxos
- Introduction
- Contribution: BP Fast Paxos
- References
- Brief Announcement: On the Meaning of Solving a Task with a Failure Detector
- References
- Brief Announcement: Algorithmic Mechanisms for Internet-Based Computing under Unreliable Communication
- Motivation and Prior Work
- Contributions
- References
- Fault-Tolerance and Security (Session 1e)
- Maximum Metric Spanning Tree Made Byzantine Tolerant
- Introduction
- Model, Definitions and Previous Results
- State Model
- Self-Stabilizing Protocols Resilient to Byzantine Faults
- Maximum Metric Tree Construction
- Previous Results
- Impossibility Results
- Topology-Aware Strongly Stabilizing Protocol
- Presentation of the Protocol
- Proof of the (t,S$_B^*$,n-1)-TA Strong Stabilization for spec
- Concluding Remarks
- References
- Performing Dynamically Injected Tasks on Processes Prone to Crashes and Restarts
- Introduction
- Model
- Solutions Guaranteeing Correctness
- Central Scheduler
- Central Injector
- Local Injector
- Solutions Guaranteeing Fairness
- Central Scheduler
- Central Injector
- Local Injector
- Extensions and Limitations
- Solutions under Restricted Communication
- Non-unit-Length Tasks
- Future Directions
- References
- Leakage-Resilient Coin Tossing
- Introduction
- Our Contributions
- Overview of Our Solution
- Background and Definitions
- Verifiable Secret Sharing
- Robust Multi-source Extractors
- Feige Committee Election Protocol
- Modeling Leakage in Distributed Protocols
- Verifiable Secret Sharing with Leakage
- Disjoint Committee Election
- Unbiased Coin Tossing with Leakage
- References
- Brief Announcements II (Session 1f)
- Brief Announcement: Composition Games for Distributed Systems: The EU Grants Games
- References
- Brief Announcement: Distributed Approximations for the Semi-matching Problem
- References
- Brief Announcement: Opportunistic Information Dissemination in Mobile Ad-Hoc Networks
- References
- Brief Announcement: Bridging the Theory-Practice Gap in Multi-commodity Flow Routing
- Introduction
- Existing Models: Theory vs. Practice
- Routers Plus Pre-processing (RPP) Model
- Algorithms
- References
- Invited Lecture: Paxos Plus (Session 2a)
- DISC 2011 Invited Lecture by Dahlia Malkhi: Going beyond Paxos
- Byzantizing Paxos by Refinement
- Introduction
- Consensus and Classic Paxos
- Consensus
- Paxos Consensus
- Byzantizing an Algorithm
- Algorithm PCon
- Algorithm BPCon
- Liveness and Learning about Sent Messages
- Sending Proofs
- Relaying 1b Messages
- The Castro-Liskov Algorithm
- The Formal Specifications and Proof
- Conclusion
- References
- Wireless (Session 2b)
- Unbounded Contention Resolution in Multiple-Access Channels
- Introduction
- Preliminaries
- One-Fail Adaptive
- Exp Back-on/Back-off
- Evaluation
- Conclusions and Open Problems
- References
- Deterministic and Energy-Optimal Wireless Synchronization
- Introduction
- Preliminaries
- Synchronization Algorithms for Single-Hop Networks
- Conclusion
- References
- Leveraging Channel Diversity to Gain Efficiency and Robustness for Wireless Broadcast
- Introduction
- Model
- Upper Bound for No Disruption
- Upper Bound for Disruption and Common Randomness
- Upper Bound for Disruption and No Common Randomness
- Lower Bounds
- Conclusion and Future Work
- References
- Leader Election Using Loneliness Detection
- Introduction
- System Models, Definitions, and Notations
- The Leader Election Problem
- The Loneliness Detection Problem
- Algorithms and Lower Bounds for Loneliness Detection
- Upper Bounds for LD in WCD Systems
- Lower Bounds for LD in WCD Systems
- Revisiting SCD on WCD Systems
- Algorithms and Lower Bounds for Leader Election
- Upper Bounds for LE in SCD Systems
- Lower Bounds for LE in Both SCD and WCD Systems
- Leader Election in Weak Collision Detection Systems
- References
- Network algorithms I (Session 2c)
- Optimal Random Sampling from Distributed Streams Revisited
- Introduction
- Our Results
- Related Work
- Model
- Algorithm
- Correctness
- Analysis of the Algorithm (Upper Bound)
- Lower Bound
- Sampling with Replacement
- References
- Parsimonious Flooding in Geometric Random-Walks
- Introduction
- Preliminaries
- High Transmission-Rate or Low-Mobility
- Proof of Theorem 2
- Medium Transmission-Rate or Medium Mobility
- Proof of Theorem 3
- Low Transmission-Rate or High Mobility
- Proof of Theorem 4
- The Multi-source Case and the Completion Threshold
- Conclusions
- References
- Misleading Stars: What Cannot Be Measured in the Internet?
- Introduction
- Related Work
- Our Contribution
- Model
- Inferrable Topologies
- Basic Observations
- Properties
- Full Exploration
- Conclusion
- References
- Brief Announcements III (Session 2d)
- Brief Announcement: A Randomized Algorithm for Label Assignment in Dynamic Networks
- References
- Brief Announcement: ?O: Specifying an Eventual Leader Service for Dynamic Systems
- System Model and Specification of ?O
- References
- Brief Announcement: The BG-Simulation for Byzantine Mobile Robots
- References
- Invited Lecture & Best Paper: Aspects of Locality(Session 3a)
- DISC 2011 Invited Lecture: Polygon Reconstruction with Little Information: An Example for the Power of Simple Micro-robots
- Locality and Checkability in Wait-Free Computing
- Introduction
- Model
- Projection-Closeness and Wait-Free Checkability
- Locality-Preserving Tasks
- References
- Consensus (Session 3b)
- The Contest between Simplicity and Efficiency in Asynchronous Byzantine Agreement
- Introduction
- Preliminaries
- Fully Symmetric Round Protocols
- Impossibility of Polynomial Time for Fully Symmetric Round Protocols
- Completing the Proof of Theorem 1
- Directions for Future Work
- References
- Randomized Consensus in Expected O(n$^2$) Total Work Using Single-Writer Registers
- Introduction
- Prior Work
- Our Approach
- The Shared Coin Protocol
- Analysis
- Overview of the Proof
- Deterministic Bounds on Error and Running Time
- Common Votes and Extra Votes
- Bound on Common Votes
- Bound on Extra Votes
- Full Result
- Conclusions
- References
- Structured Derivation of Semi-Synchronous Algorithms
- Introduction
- Preliminaries
- Timely Announced Broadcast
- Terminating Reliable Broadcast from TAB
- Set Consensus from TAB
- Summary
- References
- Byzantine Agreement Using Partial Authentication
- Introduction
- Motivating Example
- Model and Contributions
- Results and Contributions
- The Good: When the Honest Are in Abundance
- The Bad: When Faulty Outnumber the Honest
- ?: The Baby Protocol
- Beyond 2-Connected Networks
- The Ugly: When Only the Faulty can Authenticate
- Concluding Remarks
- References
- Network algorithms II (Session 3c)
- On Approximate Distance Labels and Routing Schemes with Affine Stretch
- Introduction
- Fast Approximate Distance Labeling
- Compact Routing
- Conclusion
- References
- The Complexity of Data Aggregation in Directed Networks
- Introduction
- Background and Related Work
- Preliminaries
- Approximate and Exact Counting
- Computing Sensitive Functions
- Lower Bounds on Computing a Sensitive Function
- A (D + ( n / B))-Round Algorithm for HF$_n$
- Conclusion
- References
- Black Hole Search with Finite Automata Scattered in a Synchronous Torus
- Introduction
- Our Model
- Impossibility Results
- Agents with Unmovable Tokens
- Agents with Movable Tokens
- Algorithms for BHS in a Torus using Movable Tokens
- Solving BHS Using k=3 Agents and 3 Tokens
- BHS Using k=4 Agents and 2 Tokens Each
- BHS with 3 Agents and 2 Movable Tokens
- Conclusions
- References
- Synchronous Rendezvous for Location-Aware Agents
- Introduction
- Linear Time Rendezvous on the Infinite Line
- Linear Time Rendezvous in Trees
- One-Way Rendezvous in the Half-Line
- Rendezvous in trees
- Rendezvous in the Higher-Dimensional Space
- Rendezvous in Arbitrary Graphs
- References
- Concurrency (Session 3d)
- Toward a Formal Semantic Framework for Deterministic Parallel Programming
- Introduction
- System Model
- Example Definitions of Equivalence
- Discussion
- Containment Properties
- Programming Languages and Idioms
- Repetitive Debugging
- Deterministic Implementations
- Conclusions and Future Work
- References
- CAFE´ : Scalable Task Pools with Adjustable Fairness and Contention
- Introduction
- Related Work
- CAFÉ: A Task Pool with Adjustable Fairness
- TreeContainer
- Combining TreeContainers in a FIFO List
- CAFÉ's Properties
- Safety Properties
- Performance Properties
- Evaluation
- Experiment Setup
- System Throughput
- Choosing the Tree Height
- Conclusions
- References
- Oblivious Collaboration
- Introduction
- Related Work
- Discussion
- The Oblivious Model
- Impossibility of MC(n,2n-2)
- Cyclic Finite Programs or Words
- Simplified Oblivious Model for MC and AR
- An Oblivious MC Algorithm with 2n-1 Chairs
- Preliminaries
- The MC(n,2n-1) Upper Bound
- The Oblivious AR(n,2n-1) Algorithm
- Oblivious MC Algorithms by the Probabilistic Method
- Permutations over O(n) Chairs
- Open Problems
- References
- Author Index
