# Introduction to Distributed Algorithms

Cambridge University Press, Sep 28, 2000 - Computers - 596 pages
Distributed 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 References 572 Index 587 Copyright

### References to this book

 Distributed AlgorithmsNancy A. LynchLimited preview - 1996
All Book Search results &raquo;