Impossibility Results for Distributed Computing

Book description


To understand the power of distributed systems, it is necessary to understand their inherent limitations: what problems cannot be solved in particular systems, or without sufficient resources (such as time or space). This book presents key techniques for proving such impossibility results and applies them to a variety of different problems in a variety of different system models. Insights gained from these results are highlighted, aspects of a problem that make it difficult are isolated, features of an architecture that make it inadequate for solving certain problems efficiently are identified, and different system models are compared.

Table of Contents: Acknowledgments / Introduction / Indistinguishability / Shifting and Scaling / Scenario Arguments / Information Theory Arguments / Covering Arguments / Valency Arguments / Combinatorial Arguments / Reductions and Simulations / Bibliography / Authors' Biographies

Table of contents

  1. Introduction
    1. Unsolvability Results and Lower Bounds
    2. Why Study Impossibility Results?
    3. Structure of the Book
  2. Indistinguishability
    1. A Time Tradeoff Between READ and WRITE in the Implementation of a Register
    2. A Space Lower Bound for First-Come First-Served Mutual Exclusion
    3. A Lower Bound on the Step Complexity of Approximate Agreement
    4. Chain Arguments for Consensus
    5. Causality Arguments
  3. Shifting and Scaling
    1. Shifting Arguments
    2. Time Lower Bounds for Implementing a Multi-Writer Register
    3. Clock Synchronization without Drift
    4. Scaling Arguments
    5. Clock Synchronization with Drift
  4. Scenario Arguments
    1. Impossibility of Consensus with Arbitrary Process Failures
    2. Clock Synchronization with Arbitrary Process Failures
  5. Information Theory Arguments
    1. Lower Bounds using Single-Writer Registers
    2. The Round Complexity of OR
    3. The Round Complexity of Approximate Agreement
    4. Lower Bounds using More Powerful Objects
    5. The Round Complexity of Collect
    6. A Step Complexity Tradeoff for Synchronous Snapshots
  6. Covering Arguments
    1. A Space Lower Bound for Mutual Exclusion
    2. The Space Complexity of Timestamps
    3. Space and Step Complexity Lower Bounds for the Implementation of a Counter using Swap Objects
    4. A Lower Bound on Step Complexity for Space-Optimal Implementations of a Multi-Writer Snapshot (1/2)
    5. A Lower Bound on Step Complexity for Space-Optimal Implementations of a Multi-Writer Snapshot (2/2)
    6. A Lower Bound on the Number of Stalls Incurred by a Counter Implemented using Arbitrary Read-Modify-Write Primitives
  7. Valency Arguments
    1. The Unsolvability of Consensus using m-assignment
    2. The Round Complexity of Consensus
    3. The Unsolvability of Consensus in Asynchronous Message Passing Systems
    4. The Space Complexity of Consensus
      1. Anonymous Processes
      2. The General Case (1/2)
      3. The General Case (2/2)
    5. A Lower Bound on Expected Work for Randomized Consensus
      1. Chain Arguments
      2. Nullvalent Executions
      3. Bivalent Executions (1/2)
      4. Bivalent Executions (2/2)
      5. Putting the Pieces Together
  8. Combinatorial Arguments
    1. Unsolvability of Set Consensus
    2. A Lower Bound on UPDATE Time for a Single-Writer Snapshot
    3. A Lower Bound on the Solo Step Complexity of Weak Test&Set using Turán's Theorem
    4. Anonymous Conflict Detectors
    5. Yao's Principle
    6. Expected Step Complexity of Randomized Implementations of a Max Register (1/2)
    7. Expected Step Complexity of Randomized Implementations of a Max Register (2/2)
  9. Reductions and Simulations
    1. Simulations with Different Numbers of Processes
    2. The BG Simulation
    3. Round-by-Round Simulations
    4. Uncomputability of Consensus Number
  10. Bibliography (1/2)
  11. Bibliography (2/2)
  12. Authors' Biographies (1/2)
  13. Authors' Biographies (2/2)

Product information

  • Title: Impossibility Results for Distributed Computing
  • Author(s): Hagit Attiya, Faith Ellen
  • Release date: May 2014
  • Publisher(s): Morgan & Claypool Publishers
  • ISBN: 9781627051712