Introduction to Distributed Algorithms

Predný obal
Cambridge 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
References
572
Index
587
Autorské práva

Iné vydania - Zobraziť všetky

Časté výrazy a frázy

Bibliografické informácie