## Introduction to Distributed AlgorithmsDistributed algorithms have been the subject of intense development over the last twenty years. The second edition of this successful textbook provides an up-to-date introduction both to the topic, and to the theory behind the algorithms. The clear presentation makes the book suitable for advanced undergraduate or graduate courses, whilst the coverage is sufficiently deep to make it useful for practising engineers and researchers. The author concentrates on algorithms for the point-to-point message passing model, and includes algorithms for the implementation of computer communication networks. Other key areas discussed are algorithms for the control of distributed applications (wave, broadcast, election, termination detection, randomized algorithms for anonymous networks, snapshots, deadlock detection, synchronous systems), and fault-tolerance achievable by distributed algorithms. The two new chapters on sense of direction and failure detectors are state-of-the-art and will provide an entry to research in these still-developing topics. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Introduction Distributed Systems | 1 |

11 What is a Distributed System? | 2 |

12 Architecture and Languages | 18 |

13 Distributed Algorithms | 26 |

14 Outline of the Book | 36 |

Protocols | 41 |

The Model | 43 |

21 Transition Systems and Algorithms | 44 |

Exercises to Chapter 9 | 332 |

Snapshots | 335 |

101 Preliminaries | 336 |

102 Two Snapshot Algorithms | 340 |

103 Using Snapshot Algorithms | 344 |

Deadlock Detection | 349 |

Exercises to Chapter 10 | 355 |

Sense of Direction and Orientation | 356 |

22 Proving Properties of Transition Systems | 50 |

23 Causal Order of Events and Logical Clocks | 54 |

24 Additional Assumptions Complexity | 64 |

Exercises to Chapter 2 | 71 |

Communication Protocols | 74 |

31 The Balanced Slidingwindow Protocol | 76 |

32 A Timerbased Protocol | 85 |

Exercises to Chapter 3 | 101 |

Routing Algorithms | 103 |

41 Destinationbased Routing | 105 |

42 The Allpairs Shortestpath Problem | 110 |

43 The Netchange Algorithm | 123 |

44 Routing with Compact Routing Tables | 132 |

45 Hierarchical Routing | 149 |

Exercises to Chapter 4 | 153 |

Deadlockfree Packet Switching | 155 |

51 Introduction | 156 |

52 Structured Solutions | 158 |

53 Unstructured Solutions | 167 |

54 Further Issues | 171 |

Exercises to Chapter 5 | 176 |

Fundamental Algorithms | 179 |

Wave and Traversal Algorithms | 181 |

61 Definition and Use of Wave Algorithms | 182 |

62 A Collection of Wave Algorithms | 190 |

63 Traversal Algorithms | 202 |

Depthfirst Search | 208 |

65 Remaining Issues | 217 |

Exercises to Chapter 6 | 224 |

Election Algorithms | 227 |

71 Introduction | 228 |

72 Ring Networks | 232 |

73 Arbitrary Networks | 245 |

74 The KorachKuttenMoran Algorithm | 260 |

Exercises to Chapter 7 | 266 |

Termination Detection | 268 |

81 Preliminaries | 270 |

82 Computation Trees and Forests | 276 |

83 Wavebased Solutions | 284 |

84 Other Solutions | 299 |

Exercises to Chapter 8 | 305 |

Anonymous Networks | 307 |

91 Preliminaries | 309 |

92 Deterministic Algorithms | 317 |

93 A Probabilistic Election Algorithm | 323 |

94 Computing the Network Size | 327 |

111 Introduction and Definitions | 357 |

112 Election in Rings and Chordal Rings | 364 |

113 Computing in Hypercubes | 374 |

114 Complexityrelated Issues | 386 |

115 Conclusions and Open Questions | 392 |

Exercises to Chapter 11 | 394 |

Synchrony in Networks | 396 |

121 Preliminaries | 397 |

122 Election in Synchronous Networks | 404 |

123 Synchronizer Algorithms | 408 |

Breadthfirst Search | 414 |

125 The Archimedean Assumption | 420 |

Exercises to Chapter 12 | 421 |

Fault Tolerance | 425 |

Fault Tolerance in Distributed Systems | 427 |

132 Robust Algorithms | 429 |

133 Stabilizing Algorithms | 435 |

Fault Tolerance in Asynchronous Systems | 437 |

142 Initially Dead Processes | 442 |

143 Deterministically Achievable Cases | 445 |

144 Probabilistic Consensus Algorithms | 451 |

145 Weak Termination | 462 |

Exercises to Chapter 14 | 466 |

Fault Tolerance in Synchronous Systems | 469 |

151 Synchronous Decision Protocols | 470 |

152 Authenticating Protocols | 481 |

153 Clock Synchronization | 493 |

Exercises to Chapter 15 | 502 |

Failure Detection | 505 |

161 Model and Definitions | 506 |

162 Solving Consensus with a Weakly Accurate Detector | 510 |

163 Eventually Weakly Accurate Detectors | 511 |

164 Implementation of Failure Detectors | 515 |

Exercises to Chapter 16 | 518 |

Stabilization | 520 |

171 Introduction | 521 |

172 Graph Algorithms | 526 |

173 Methodology for Stabilization | 535 |

Exercises to Chapter 17 | 547 |

Appendices | 549 |

A Pseudocode Conventions | 551 |

B Graphs and Networks | 556 |

572 | |

587 | |

### Other editions - View all

### Common terms and phrases

active assumed assumption basic computation begin receive breadth-first search broadcast buffer channel Chapter clique clock cluster connected correct processes deadlock decision defined Definition denoted depth-first search destination detection deterministic deterministic algorithm distributed algorithm distributed computation distributed system election algorithm end Algorithm end end estp event execution Exercise exists failure detector father fifo finite forall frond graph hence hypercube identity implies init initial configuration input integer label layer Lemma message complexity message passing message sent neighbor Neighp node number of messages packet passive path possible probabilistic probabilistic algorithm problem process q processes decide processor Proof protocol pulse receipt requires ring rithm round routing tables Section send tok sends a message sense of direction sequence simple path snapshot snapshot algorithm spanning tree statep Subsection synchronous terminal configuration Theorem topology transition udef undirected graph variable wave algorithm