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
鄂公網(wǎng)安備 42010302001612號(hào) 