Introduction to Distributed AlgorithmsCambridge University Press, 28. 9. 2000 - 596 strán (strany) 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. |
Obsah
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 | |
Iné vydania - Zobraziť všetky
Časté výrazy a frázy
active assumed assumption basic computation begin receive breadth-first search broadcast buffer channel Chapter clique clock cluster communication connected correct processes deadlock decision defined Definition denoted depth-first search destination detection deterministic deterministic algorithm distributed algorithm Distributed Computing distributed system Du[v election algorithm event execution Exercise exists failure detector father fifo finite Floyd-Warshall algorithm forall frond graph hence hypercube identity implies init initial configuration input integer label layer Lemma lower bound message complexity message passing message sent Neigh neighbor node number of messages packet passive path possible probabilistic probabilistic algorithm problem process q processes decide processor Proof protocol pulse receipt recp 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 variable wave algorithm