| |
| |
| |
| Introduction | |
| |
| |
| |
| Distributed Systems | |
| |
| |
| |
| Theory of Distributed Computing | |
| |
| |
| |
| Overview | |
| |
| |
| |
| Relationship of Theory to Practice | |
| |
| |
| |
| Fundamentals | |
| |
| |
| |
| Basic Algorithms in Message-Passing Systems | |
| |
| |
| |
| Formal Models for Message Passing Systems | |
| |
| |
| |
| Systems | |
| |
| |
| |
| Complexity Measures | |
| |
| |
| |
| Pseudocode Conventions | |
| |
| |
| |
| Broadcast and Convergecast on a Spanning Tree | |
| |
| |
| |
| Flooding and Building a Spanning Tree | |
| |
| |
| |
| Constructing a Depth-First Search Spanning Tree for a Specified Root | |
| |
| |
| |
| Constructing a Depth-First Search Spanning Tree without a Specified Root | |
| |
| |
| |
| Leader Election in Rings | |
| |
| |
| |
| The Leader Election Problem | |
| |
| |
| |
| Anonymous Rings | |
| |
| |
| |
| Asynchronous Rings | |
| |
| |
| |
| An O(n[superscript 2]) Algorithm | |
| |
| |
| |
| An O(n log n) Algorithm | |
| |
| |
| |
| An [Omega](n log n) Lower Bound | |
| |
| |
| |
| Synchronous Rings | |
| |
| |
| |
| An O(n) Upper Bound | |
| |
| |
| |
| An [Omega](n log n) Lower Bound for Restricted Algorithms | |
| |
| |
| |
| Mutual Exclusion in Shared Memory | |
| |
| |
| |
| Formal Model for Shared Memory Systems | |
| |
| |
| |
| Systems | |
| |
| |
| |
| Complexity Measures | |
| |
| |
| |
| Pseudocode Conventions | |
| |
| |
| |
| The Mutual Exclusion Problem | |
| |
| |
| |
| Mutual Exclusion Using Powerful Primitives | |
| |
| |
| |
| Binary Test&Set Registers | |
| |
| |
| |
| Read-Modify-Write Registers | |
| |
| |
| |
| Lower Bound on the Number of Memory States | |
| |
| |
| |
| Mutual Exclusion Using Read/Write Registers | |
| |
| |
| |
| The Bakery Algorithm | |
| |
| |
| |
| A Bounded Mutual Exclusion Algorithm for Two Processors | |
| |
| |
| |
| A Bounded Mutual Exclusion Algorithm for n Processors | |
| |
| |
| |
| Lower Bound on the Number of Read/Write Registers | |
| |
| |
| |
| Fast Mutual Exclusion | |
| |
| |
| |
| Fault-Tolerant Consensus | |
| |
| |
| |
| Synchronous Systems with Crash Failures | |
| |
| |
| |
| Formal Model | |
| |
| |
| |
| The Consensus Problem | |
| |
| |
| |
| A Simple Algorithm | |
| |
| |
| |
| Lower Bound on the Number of Rounds | |
| |
| |
| |
| Synchronous Systems with Byzantine Failures | |
| |
| |
| |
| Formal Model | |
| |
| |
| |
| The Consensus Problem Revisited | |
| |
| |
| |
| Lower Bound on the Ratio of Faulty Processors | |
| |
| |
| |
| An Exponential Algorithm | |
| |
| |
| |
| A Polynomial Algorithm | |
| |
| |
| |
| Impossibility in Asynchronous Systems | |
| |
| |
| |
| Shared Memory--The Wait-Free Case | |
| |
| |
| |
| Shared Memory--The General Case | |
| |
| |
| |
| Message Passing | |
| |
| |
| |
| Causality and Time | |
| |
| |
| |
| Capturing Causality | |
| |
| |
| |
| The Happens-Before Relation | |
| |
| |
| |
| Logical Clocks | |
| |
| |
| |
| Vector Clocks | |
| |
| |
| |
| Shared Memory Systems | |
| |
| |
| |
| Examples of Using Causality | |
| |
| |
| |
| Consistent Cuts | |
| |
| |
| |
| A Limitation of the Happens-Before Relation: The Session Problem | |
| |
| |
| |
| Clock Synchronization | |
| |
| |
| |
| Modeling Physical Clocks | |
| |
| |
| |
| The Clock Synchronization Problem | |
| |
| |
| |
| The Two Processors Case | |
| |
| |
| |
| An Upper Bound | |
| |
| |
| |
| A Lower Bound | |
| |
| |
| |
| Practical Clock Synchronization: Estimating Clock Differences | |
| |
| |
| |
| Simulations | |
| |
| |
| |
| A Formal Model for Simulations | |
| |
| |
| |
| Problem Specifications | |
| |
| |
| |
| Communication Systems | |
| |
| |
| |
| Asynchronous Point-to-Point Message Passing | |
| |
| |
| |
| Asynchronous Broadcast | |
| |
| |
| |
| Processes | |
| |
| |
| |
| Admissibility | |
| |
| |
| |
| Simulations | |
| |
| |
| |
| Pseudocode Conventions | |
| |
| |
| |
| Broadcast and Multicast | |
| |
| |
| |
| Specification of Broadcast Services | |
| |
| |
| |
| The Basic Service Specification | |
| |
| |
| |
| Broadcast Service Qualities | |
| |
| |
| |
| Implementing a Broadcast Service | |
| |
| |
| |
| Basic Broadcast Service | |
| |
| |
| |
| Single-Source FIFO Ordering | |
| |
| |
| |
| Totally Ordered Broadcast | |
| |
| |
| |
| Causality | |
| |
| |
| |
| Reliability | |
| |
| |
| |
| Multicast in Groups | |
| |
| |
| |
| Specification | |
| |
| |
| |
| Implementation | |
| |
| |
| |
| An Application: Replication | |
| |
| |
| |
| Replicated Database | |
| |
| |
| |
| The State Machine Approach | |
| |
| |
| |
| Distributed Shared Memory | |
| |
| |
| |
| Linearizable Shared Memory | |
| |
| |
| |
| Sequentially Consistent Shared Memory | |
| |
| |
| |
| Algorithms | |
| |
| |
| |
| Linearizability | |
| |
| |
| |
| Sequential Consistency | |
| |
| |
| |
| Lower Bounds | |
| |
| |
| |
| Adding Time and Clocks to the Layered Model | |
| |
| |
| |
| Sequential Consistency | |
| |
| |
| |
| Linearizability | |
| |
| |
| |
| Fault-Tolerant Simulations of Read/Write Objects | |
| |
| |
| |
| Fault-Tolerant Shared Memory Simulations | |
| |
| |
| |
| Simple Read/Write Register Simulations | |
| |
| |
| |
| Multi-Valued from Binary | |
| |
| |
| |
| Multi-Reader from Single-Reader | |
| |
| |
| |
| Multi-Writer from Single-Writer | |
| |
| |
| |
| Atomic Snapshot Objects | |
| |
| |
| |
| Handshaking Procedures | |
| |
| |
| |
| A Bounded Memory Simulation | |
| |
| |
| |
| Simulating Shared Registers in Message-Passing Systems | |
| |
| |
| |
| Simulating Synchrony | |
| |
| |
| |
| Synchronous Message-Passing Specification | |
| |
| |
| |
| Simulating Synchronous Processors | |
| |
| |
| |
| Simulating Synchronous Processors and Synchronous Communication | |
| |
| |
| |
| A Simple Synchronizer | |
| |
| |
| |
| Application: Constructing a Breadth-First Search Tree | |
| |
| |
| |
| Local vs. Global Simulations | |
| |
| |
| |
| Improving the Fault Tolerance of Algorithms | |
| |
| |
| |
| Overview | |
| |
| |
| |
| Modeling Synchronous Processors and Byzantine Failures | |
| |
| |
| |
| Simulating Identical Byzantine Failures on Top of Byzantine Failures | |
| |
| |
| |
| Definition of Identical Byzantine | |
| |
| |
| |
| Simulating Identical Byzantine | |
| |
| |
| |
| Simulating Omission Failures on Top of Identical Byzantine Failures | |
| |
| |
| |
| Definition of Omission | |
| |
| |
| |
| Simulating Omission | |
| |
| |
| |
| Simulating Crash Failures on Top of Omission Failures | |
| |
| |
| |
| Definition of Crash | |
| |
| |
| |
| Simulating Crash | |
| |
| |
| |
| Application: Consensus in the Presence of Byzantine Failures | |
| |
| |
| |
| Asynchronous Identical Byzantine on Top of Byzantine Failures | |
| |
| |
| |
| Definition of Asynchronous Identical Byzantine | |
| |
| |
| |
| Definition of Asynchronous Byzantine | |
| |
| |
| |
| Simulating Asynchronous Identical Byzantine | |
| |
| |
| |
| Fault-Tolerant Clock Synchronization | |
| |
| |
| |
| Problem Definition | |
| |
| |
| |
| The Ratio of Faulty Processors | |
| |
| |
| |
| A Clock Synchronization Algorithm | |
| |
| |
| |
| Timing Failures | |
| |
| |
| |
| Byzantine Failures | |
| |
| |
| |
| Practical Clock Synchronization: Identifying Faulty Clocks | |
| |
| |
| |
| Advanced Topics | |
| |
| |
| |
| Randomization | |
| |
| |
| |
| Leader Election: A Case Study | |
| |
| |
| |
| Weakening the Problem Definition | |
| |
| |
| |
| Synchronous One-Shot Algorithm | |
| |
| |
| |
| Synchronous Iterated Algorithm and Expectation | |
| |
| |
| |
| Asynchronous Systems and Adversaries | |
| |
| |
| |
| Impossibility of Uniform Algorithms | |
| |
| |
| |
| Summary of Probabilistic Definitions | |
| |
| |
| |
| Mutual Exclusion with Small Shared Variables | |
| |
| |
| |
| Consensus | |
| |
| |
| |
| The General Algorithm Scheme | |
| |
| |
| |
| A Common Coin with Constant Bias | |
| |
| |
| |
| Tolerating Byzantine Failures | |
| |
| |
| |
| Shared Memory Systems | |
| |
| |
| |
| Wait-Free Simulations of Arbitrary Objects | |
| |
| |
| |
| Example: A FIFO Queue | |
| |
| |
| |
| The Wait-Free Hierarchy | |
| |
| |
| |
| Universality | |
| |
| |
| |
| A Nonblocking Simulation Using Compare&Swap | |
| |
| |
| |
| A Nonblocking Algorithm Using Consensus Objects | |
| |
| |
| |
| A Wait-Free Algorithm Using Consensus Objects | |
| |
| |
| |
| Bounding the Memory Requirements | |
| |
| |
| |
| Handling Nondeterminism | |
| |
| |
| |
| Employing Randomized Consensus | |
| |
| |
| |
| Problems Solvable in Asynchronous Systems | |
| |
| |
| |
| k-Set Consensus | |
| |
| |
| |
| Approximate Agreement | |
| |
| |
| |
| Known Input Range | |
| |
| |
| |
| Unknown Input Range | |
| |
| |
| |
| Renaming | |
| |
| |
| |
| The Wait-Free Case | |
| |
| |
| |
| The General Case | |
| |
| |
| |
| Long-Lived Renaming | |
| |
| |
| |
| k-Exclusion and k-Assignment | |
| |
| |
| |
| An Algorithm for k-Exclusion | |
| |
| |
| |
| An Algorithm for k-Assignment | |
| |
| |
| |
| Solving Consensus in Eventually Stable Systems | |
| |
| |
| |
| Preserving Safety in Shared Memory Systems | |
| |
| |
| |
| Failure Detectors | |
| |
| |
| |
| Solving Consensus using Failure Detectors | |
| |
| |
| |
| Solving Consensus with [diamond]S | |
| |
| |
| |
| Solving Consensus with S | |
| |
| |
| |
| Solving Consensus with [Omega] | |
| |
| |
| |
| Implementing Failure Detectors | |
| |
| |
| |
| State Machine Replication with Failure Detectors | |
| |
| |
| References | |
| |
| |
| Index | |