1 Introduction: Distributed Systems
1.1 What is a Distributed System?
1.2 Architecture and Languages
1.3 Distributed Algorithms
1.4 Outline of the Book
Part One: Protocols
2 The Model
2.1 Transition Systems and Algorithms
2.2 Proving Properties of Transition Systems
2.3 Causal Order of Events and Logical Clocks
2.4 Additional Assumptions, Complexity
Exercises to Chapter 2
3 Communication Protocols
3.1 The Balanced Sliding-window Protocol
3.2 A Timer-based Protocol
Exercises to Chapter 3
4 Routing Algorithms
4.1 Destination-based Routing
4.2 The AU-pairs Shortest-path Problem
4.3 The Netchange Algorithm
4.4 Routing with Compact Routing Tables
4.5 Hierarchical Routing
Exercises to Chapter 4
5 Deadlock-free Packet Switching
5.1 Introduction
5.2 Structured Solutions
5.3 Unstructured Solutions
5.4 Further Issues
Exercises to Chapter 5
Part Two: Fundamental Algorithms
6 Wave and Traversed Algorithms
6.1 Definition and Use of Wave Algorithms
6.2 A Collection of Wave Algorithms
6.3 Traversal Algorithms
6.4 Time Complexity: Depth-first Search
6.5 Remaining Issues
Exercises to Chapter 6
7 Election Algorithms
7.1 Introduction
7.2 Ring Networks
7.3 Arbitrary Networks
7.4 The Korach-Kutten-Moran Algorithm
Exercises to Chapter 7
8 Termination Detection
8.1 Preliminaries
8.2 Computation Trees and Forests
8.3 Wave-based Solutions
8.4 Other Solutions
Exercises to Chapter 8
9 Anonymous Networks
9.1 Preliminaries
9.2 Deterministic Algorithms
9.3 A Probabilistic Election,Algorithm
9.4 Computing the Network Size
Exercises to Chapter 9
10 Snapshots
10.1 Preliminaries
10.2 Two Snapshot Algorithms
10.3 Using Snapshot Algorithms
10.4 Application: Deadlock Detection
Exercises to Chapter 10
11 Sense of Direction and Orientation
11.1 Introduction and Definitions.
11.2 Election in Rings and Chordal Rings
11.3 Computing in Hypercubes
11.4 Complexity-related Issues
11.5 Conclusions and Open Questions
Exercises to Chapter 11
12 Synchrony in Networks
12.1 Preliminaries
12.2 Election in Synchronous Networks
12.3 Synchronizer Algorithms
12.4 Application: Breadth-first Search
12.5 The Archimedean Assumption
Exercises to Chapter 12
Part Three: Fault Tolerance
13 Fault Tolerance in Distributed Systems
13.1 Reasons for Using Fault-tolerant Algorithms
13.2 Robust Algorithms
13.3 Stabilizing Algorithms
14 Fault Tolerance in Asynchronous Systems
14.1 Impossibility of Consensus
14.2 Initially Dead Processes
14.3 Deterministically Achievable Cases
14.4 Probabilistic Consensus Algorithms
14.5 Weak Termination
Exercises to Chapter 14
15 Fault Tolerance in Synchronous Systems
15.1 Synchronous Decision Protocols
15.2 Authenticating Protocols
15.3 Clock Synchronization
Exercises to Chapter 15
16 Failure Detection
16.1 Model and Definitions
16.2 Solving Consensus with a Weakly Accurate Detector
16.3 Eventually Weakly Accurate Detectors
16.4 Implementation of Failure Detectors
Exercises to Chapter 16
17 Stabilization
17.1 Introduction
17.2 Graph Algorithms
17.3 Methodology for Stabilization
Exercises to Chapter 17
Part Four: Appendices
A Pseudocode Conventions
B Graphs and Networks
References
Index
鄂公网安备 42010302001612号 