Distributed Algorithms
- 1st Edition - March 1, 1996
- Imprint: Morgan Kaufmann
- Author: Nancy A. Lynch
- Language: English
- Hardback ISBN:9 7 8 - 1 - 5 5 8 6 0 - 3 4 8 - 6
- Paperback ISBN:9 7 8 - 0 - 1 2 - 3 9 5 4 5 4 - 1
- eBook ISBN:9 7 8 - 0 - 0 8 - 0 5 0 4 7 0 - 4
In Distributed Algorithms, Nancy Lynch provides a blueprint for designing, implementing, and analyzing distributed algorithms. She directs her book at a wide audience, including… Read more
Purchase options
Institutional subscription on ScienceDirect
Request a sales quoteIn Distributed Algorithms, Nancy Lynch provides a blueprint for designing, implementing, and analyzing distributed algorithms. She directs her book at a wide audience, including students, programmers, system designers, and researchers.
Distributed Algorithms contains the most significant algorithms and impossibility results in the area, all in a simple automata-theoretic setting. The algorithms are proved correct, and their complexity is analyzed according to precisely defined complexity measures. The problems covered include resource allocation, communication, consensus among distributed processes, data consistency, deadlock detection, leader election, global snapshots, and many others.
The material is organized according to the system model—first by the timing model and then by the interprocess communication mechanism. The material on system models is isolated in separate chapters for easy reference.
The presentation is completely rigorous, yet is intuitive enough for immediate comprehension. This book familiarizes readers with important problems, algorithms, and impossibility results in the area: readers can then recognize the problems when they arise in practice, apply the algorithms to solve them, and use the impossibility results to determine whether problems are unsolvable. The book also provides readers with the basic mathematical tools for designing new algorithms and proving new impossibility results. In addition, it teaches readers how to reason carefully about distributed algorithms—to model them formally, devise precise specifications for their required behavior, prove their correctness, and evaluate their performance with realistic measures.
Distributed Algorithmsby Nancy A. Lynch
- Preface
- 1 Introduction
- 1.1 The Subject Matter
- 1.2 Our Viewpoint
- 1.3 Overview of Chapter 2-25
- 1.4 Bibliographic Notes
- 1.5 Notation
- 2 Modelling I; Synchronous Network Model
- 2.1 Synchronous Network Systems
- 2.2 Failures
- 2.3 Inputs and Outputs
- 2.4 Executions
- 2.5 Proof Methods
- 2.6 Complexity Measures
- 2.7 Randomization
- 2.8 Bibliographic Notes
- 3 Leader Election in a Synchronous Ring
- 3.1 The Problem
- 3.2 Impossibility Result for Identical Processes
- 3.3 A Basic Algorithm
- 3.4 An algorithm with O (n log n) Communication Complexity
- 3.5 Non-Comparison-Based Algorithms
- 3.5.1 The TimeSlice Algorithm
- 3.5.2 The Variable Speeds Algorithm
- 3.6 Lower Bound for Comparison-Based Algorithms
- 3.7 Lower Bound for Non-comparison-Based Algorithms
- 3.8 Bibliographic Notes
- 3.9 Exercises
- 4 Algorithms in General Synchronous Networks
- 4.1 Leader Election in a General Network
- 4.1.1 The Problem
- 4.1.2 A Simple flooding Algorithm
- 4.1.3 Reducing the Communication Complexity
- 4.2 Breadth-First Search
- 4.2.1 The Problem
- 4.2.2 A Basic Breadth-First Search Algorithm
- 4.2.3 Applications
- 4.3 Shortest Paths
- 4.4 Minimum Spanning Tree
- 4.4.1 The Problem
- 4.4.2 Basic Theory
- 4.4.3 The Algorithm
- 4.5 Maximal Independent Set
- 4.5.1 The Problem
- 4.5.2 A Randomized Algorithm
- 4.5.3 Analysis
- 4.6 Bibliographic Notes
- 4.7 Exercises
- 4.1 Leader Election in a General Network
- 5 Distributed Consensus with Link Failures
- 5.1 The Coordinated Attack Problem - Deterministic Version
- 5.2 The Coordinated Attack Problem - Randomized Version
- 5.2.1 Formal Modelling
- 5.2.2 An Algorithm
- 5.2.3 A Lower Bound on Disagreement
- 5.3 Bibliographic Notes
- 5.4 Exercises
- 6 Distributed Consensus with Process Failures
- 6.1 The Problem
- 6.2 Algorithms for Stopping Failures
- 6.2.1 A Basic Algorithm
- 6.2.2 Reducing the Communication
- 6.2.3 Exponential Information Gathering Algorithms
- 6.2.4 Byzantine Agreement with Authentication
- 6.3 Algorithms for Byzantine Failures
- 6.3.1 An Example
- 6.3.2 EIG Algorithm for Byzantine Agreement
- 6.3.3 General Byzantine Agreement Using Binary Byzantine Agreement
- 6.3.4 Reducing the Communication Cost
- 6.4 Number of Processes for Byzantine Agreement
- 6.5 Byzantine Agreement in General Graphs
- 6.6 Weak Byzantine Agreement
- 6.7 Number of Rounds with Stopping Failures
- 6.8 Bibliographic Notes
- 6.9 Exercises
- 7 More Consensus Problems
- 7.1 k-Agreement
- 7.1.1 The Problem
- 7.1.2 An Algorithm
- 7.1.3 Lower Bound
- 7.2 Approximate Agreement
- 7.3 The Commit Problem
- 7.3.1 The Problem
- 7.3.2 Two-Phase Commit
- 7.3.3 Three-Phase Commit
- 7.3.4 Lower Bound on the Number of Messages
- 7.4 Bibliographic Notes
- 7.5 Exercises
- 7.1 k-Agreement
- 8 Modelling II: Asynchronous System Model
- 8.1 I/O Automata
- 8.2 Operations on Automata
- 8.2.1 Composition
- 8.2.2 Hiding
- 8.3 Fairness
- 8.4 Inputs and Outputs for Problems
- 8.5 Properties and Proof Methods
- 8.5.1 Invariant Assertions
- 8.5.2 Trace Properties
- 8.5.3 Safety and Liveness Properties
- 8.5.4 Compositional Reasoning
- 8.5.5 Hierarchical Proofs
- 8.6 Complexity Measures
- 8.7 Indistinguishable Executions
- 8.8 Randomization
- 8.9 Bibliographic Notes
- 8.10 Exercises
- 9 Modelling III: Asynchronous Shared Memory Model
- 9.1 Shared Memory Systems
- 9.2 Environment Model
- 9.3 Indistinguishable States
- 9.4 Shared Variable Types
- 9.5 Complexity Measures
- 9.6 Failures
- 9.7 Randomization
- 9.8 Bibliographic Notes
- 9.9 Exercises
- 10 Mutual Exclusion
- 10.1 Asynchronous Shared Memory Model
- 10.2 The Problem
- 10.3 Dijkstra's Mutual Exclusion Algorithm
- 10.3.1 The Algorithm
- 10.3.2 A Correctness Argument
- 10.3.3 An Assertional Proof of the Mutual Exclusion Condition
- 10.3.4 Running Time
- 10.4 Stronger Conditions for Mutual Exclusion Algorithms
- 10.5 Lockout-Free Mutual Exclusion Algorithms
- 10.5.1 A Two-Process Algorithm
- 10.5.2 An n-Process Algorithm
- 10.5.3 Tournament Algorithm
- 10.6 An Algorithm Using Single-Writer Shared Registers
- 10.7 The Bakery Algorithm
- 10.8 Lower Bound on the Number of Registers
- 10.8.1 Basic Facts
- 10.8.2 Single-Writer Shared Variables
- 10.8.3 Multi-Writer Shared Variables
- 10.9 Mutual Exclusion Using Read-Modify-Write Shared Variables
- 10.9.1 The Basic Problem
- 10.9.2 Bounded Bypass
- 10.9.3 Lockout-Freedom
- 10.9.4 A Simulation Proof
- 10.10 Bibliographic Notes
- 10.11 Exercises
- 11 Resource Allocation
- 11.1 The Problem
- 11.1.1 Explicit Resource Specifications and Exclusion Specifications
- 11.1.2 Resource-Allocation Problem
- 11.1.3 Dining Philosophers Problem
- 11.1.4 Restricted Form of Solutions
- 11.2 Nonexistence of Symmetric Dining Philosophers Algorithms
- 11.3 Right-Left Dining Philosophers Algorithm
- 11.3.1 Waiting Chains
- 11.3.2 The Basic Algorithm
- 11.3.3 A Generalization
- 11.4 Randomized Dining Philosophers Algorithm
- 11.4.1 The Algorithm
- 11.4.2 Correctness
- 11.5 Bibliographic Notes
- 11.1 The Problem
- 12 Consensus
- 12.1 The Problem
- 12.2. Agreement Using Read/Write Shared Memory
- 12.2.1 Restrictions
- 12.2.2 Terminology
- 12.2.3 Bivalent Initializations
- 12.2.4 Impossibility for Wait-Free Termination
- 12.2.5 Impossibility for Single-Failure Termination
- 12.3 Agreement Using Read-Modify-Write Shared Memory
- 12.4 Other Types of Shared Memory
- 12.5 Computability in Asynchronous Shared Memory Systems
- 12.6 Bibliographic Notes
- 12.7 Exercises
- 13 Atomic Objects
- 13.1 Definitions and Basic Results
- 13.1.1 Atomic Object Definition
- 13.1.2 A Canonical Wait-Free Atomic Object Automaton
- 13.1.3 Composition of Atomic Objects
- 13.1.4 Atomic Objects versus Shared Variables
- 13.1.5 A Sufficient Condition for Showing Atomicity
- 13.2 Implementing Read-Modify-Write Atomic Objects in Terms of Read/Write Variables
- 13.3 Atomic Snapshots of Shared Memory
- 13.3.1 The Problem
- 13.3.2 An Algorithm with Unbounded Variables
- 13.3.3 An Algorithm with Bounded Variables
- 13.4 Read/Write Atomic Objects
- 13.4.1 The Problem
- 13.4.2 Another Lemma for Showing Atomicity
- 13.4.3 An Algorithm with Unbounded Variables
- 13.4.4 A Bounded Algorithm Using Snapshots
- 13.5 Bibliographic Notes
- 13.6 Exercises
- 13.1 Definitions and Basic Results
- 14 Modelling IV: Asynchronous Network Model
- 14.1 Send/Receive Systems
- 14.1.1 Processes
- 14.1.2 Send/Receive Channels
- 14.1.3 Asynchronous Send/Receive Systems
- 14.1.4 Properties of Send/Receive Systems with Reliable FIFO Channels
- 14.1.5 Complexity Measures
- 14.2 Broadcast Systems
- 14.2.1 Processes
- 14.2.2 Broadcast Channel
- 14.2.3 Asynchronous Broadcast Systems
- 14.2.4 Properties of Broadcast Systems with Reliable Broadcast Channels
- 14.2.5 Complexity Measures
- 14.3 Multicast Systems
- 14.3.1 Processes
- 14.3.2 Multicast Channel
- 14.3.3. Asynchronous Multicast Systems
- 14.4 Bibliographic Notes
- 14.5 Exercises
- 14.1 Send/Receive Systems
- 15 Basic Asynchronous Network Algorithms
- 15.1 Leader Election in a Ring
- 15.1.1 The LCR Algorithm
- 15.1.2 The HS Algorithm
- 15.1.3 The Peterson Leader-Election Algorithm
- 15.1.4 A Lower Bound on Communication Complexity
- 15.2 Leader Election in an Arbitrary Network
- 15.3 Spanning Tree Construction, Broadcast and Convergecast
- 15.4 Breadth-First Search and Shortest Paths
- 15.5 Minimum Spanning Tree
- 15.5.1 Problem Statement
- 15.5.2 The Synchronous Algorithm: Review
- 15.5.3 The GHS Algorithm: Outline
- 15.5.4 In More Detail
- 15.5.5 Specific Messages
- 15.5.6. Complexity Analysis
- 15.5.7 Proving Correctness for the GHS Algorithm
- 15.5.8 A Simpler" Synchronous" Strategy
- 15.5.9 Application to Leader Election
- 15.6 Bibliographic Notes
- 15.7 Exercises
- 15.1 Leader Election in a Ring
- 16 Synchronizers
- 16.1 The Problem
- 16.2 The Local Synchronizer
- 16.3 The Safe Synchronizer
- 16.3.1 Front-End Automata
- 16.3.2 Channel Automata
- 16.3.3 The Safe Synchronizer
- 16.3.4 Correctness
- 16.4 Safe Synchronizer Implementations
- 16.4.1 Synchronizer Alpha
- 16.4.2 Synchronizer Beta
- 16.4.3 Synchronizer Gamma
- 16.5 Applications
- 16.5.1 Leader Election
- 16.5.2 Breadth-Firth Search
- 16.5.3 Shortest Paths
- 16.5.4 Broadcast and Acknowledgment
- 16.5.5 Maximal Independent Set
- 16.6 Lower Bound on Time
- 16.7 Bibliographic Notes
- 16.8 Exercises
- 17 Shared Memory versus Networks
- 17.1 Transformations from the Shared Memory Model to the Network Model
- 17.1.1 The Problem
- 17.1.2 Strategies Assuming No Failures
- 17.1.3 An algorithm Tolerating Process Failures
- 17.1.4 An Impossibility Result for n/2 Failures
- 17.2 Transformations form the Network Model to the Shared Memory Model
- 17.2.1 Send/Receive Systems
- 17.2.2 Broadcast Systems
- 17.2.3 Impossibility of Agreement in Asynchronous Networks
- 17.3 Bibliographic Notes
- 17.4 Exercises
- 17.1 Transformations from the Shared Memory Model to the Network Model
- 18 Logical Time
- 18.1 Logical Time for Asynchronous Networks
- 18.1.1 Send/ Receive Systems
- 18.1.2 Broadcast Systems
- 18.2 Adding Logical Time to Asynchronous Algorithms
- 18.2.1 Advancing the Clock
- 18.2.2 Delaying Future Events
- 18.3 Applications
- 18.3.1 Banking System
- 18.3.2 Global Snapshots
- 18.3.3 Simulating a Single State Machine
- 18.4 Transforming Real-Time Algorithms to Logical-Time Algorithms
- 18.5 Bibliographic Notes
- 18.6 Exercises
- 18.1 Logical Time for Asynchronous Networks
- 19 Global Snapshots and Stable Properties
- 19.1 Termination-Detection for Diffusing Algorithms
- 19.1.1 The Problem
- 19.1.2 The DijkstraScholten Algorithm
- 19.2 Consistent Global Snapshots
- 19.2.1 The Problem
- 19.2.2 The Chandy-Lamport Algorithm
- 19.2.3 Applications
- 19.3 Bibliographic Notes
- 19.4 Exercises
- 19.1 Termination-Detection for Diffusing Algorithms
- 20 Network Resource Allocation
- 20.1 Mutual Exclusion
- 20.1.1 The Problem
- 20.1.2 Simulating Shared Memory
- 20.1.3 Circulating Token Algorithm
- 20.1.4 An Algorithm Based on Logical Time
- 20.1.5 Improvements to the LogicalTimeME Algorithm
- 20.2 General Resource Allocation
- 20.2.1 The Problem
- 20.2.2 Coloring Algorithm
- 20.2.3 Algorithms Based on Logical Time
- 20.2.4 Acyclic Digraph Algorithm
- 20.2.5 Drinking Philosophers
- 20.3 Bibliographic Notes
- 20.4 Exercises
- 20.1 Mutual Exclusion
- 21 Asynchronous Networks with Process Failures
- 21.1 The Network Model
- 21.2 Impossibility of Agreement in the Presence of Faults
- 21.3 A Randomized Algorithm
- 21.4 Failure Detectors
- 21.5 k-Agreement
- 21.6 Approximate Agreement
- 21.7 Computability in Asynchronous Networks
- 21.8 Bibliographic Notes
- 21.9 Exercises
- 22 Data Link Protocols
- 22.1 The Problem
- 22.2 Stenning's Protocol
- 22.3 Alternating Bit Protocol
- 22.4 Bounded Tag Protocols Tolerating Reordering
- 22.4.1 Impossibility Result for Reordering and Duplication
- 22.4.2 A Bounded Tag Protocol Tolerating Loss and Reordering
- 22.4.3 Nonexistence of Efficient Protocols Tolerating Loss and Reordering
- 22.5 Tolerating Crashes
- 22.5.1 A Simple Impossibility Result
- 22.5.2 A Harder Impossibility Result
- 22.5.3 A Practical Protocol
- 22.6 Bibliographic Notes
- 22.7 Exercises
- 23 Partially Synchronous System Models
- 23.1 MMT Times Automata
- 23.1.1 Basic Definitions
- 23.1.2 Operations
- 23.2 General Timed Automata
- 23.2.1 Basic Definitions
- 23.2.2 Transforming MMT Automata into General Timed Automata
- 23.2.3 Operations
- 23.3 Properties and Proof Methods
- 23.3.1 Invariant Assertions
- 23.3.2 Timed Trace Properties
- 23.3.3 Simulations
- 23.4 Modelling Shared Memory and Network Systems
- 23.4.1 Shared Memory Systems
- 23.4.2 Networks
- 23.5 Bibliographic Notes
- 23.6 Exercises
- 23.1 MMT Times Automata
- 24 Mutual Exclusion with Partial Synchrony
- 24.1 The Problem
- 24.2 A Single-Register Algorithm
- 24.3 Resilience to Timing Failures
- 24.4. Impossibility Results
- 24.4.1 A Lower Bound on the Time
- 24.4.2 Impossibility Result for Eventual Time Bounds
- 24.5 Bibliographic Notes
- 24.6 Exercises
- 25 Consensus with Partial Synchrony
- 25.1 The Problem
- 25.2 A Failure Detector
- 25.3 Basic Results
- 25.3.1 Upper Bound
- 25.3.2 Lower Bound
- 25.4 An Efficient Algorithm
- 25.4.1 The Algorithm
- 25.4.2 Safety Properties
- 25.4.3 Liveness and Complexity
- 25.5 A Lower Bound Involving the Timing Uncertainty
- 25.6 Other Results
- 25.6.1 Synchronous Processes, Asynchronous Channels
- 25.6.2 Asynchronous Processes, Synchronous Channels
- 25.6.3 Eventual Time Bounds
- 25.7 Postscript
- 25.8 Bibliographic Notes
- 25.9 Exercises
- Bibliography
- Index
- Edition: 1
- Published: March 1, 1996
- Imprint: Morgan Kaufmann
- No. of pages: 912
- Language: English
- Hardback ISBN: 9781558603486
- Paperback ISBN: 9780123954541
- eBook ISBN: 9780080504704
NL
Nancy A. Lynch
About the author:Nancy A. Lynch is a professor of electrical engineering and computer science at MIT and heads MIT's Theory of Distributed Systems research group. She is the author of numerous research articles about distributed algorithms and impossibility results, and about formal modeling and verification of distributed systems.