Suchen und Finden
Distributed Algorithms
von: Nancy A. Lynch
Elsevier Trade Monographs, 1996
ISBN: 9780080504704 , 899 Seiten
Format: PDF, ePUB, OL
Kopierschutz: DRM
Preis: 112,00 EUR
Front Cover
1
Distributed Algorithms
4
Copyright Page
5
Contents
8
Preface
20
Chapter 1. Introduction
26
1.1 The Subject Matter
26
1.2 Our Viewpoint
29
1.3 Overview of Chapters 2-25
31
1.4 Bibliographic Notes
38
1.5 Notation
39
Part I: Synchronous Network Algorithms
40
Chapter 2. Modelling I: Synchronous Network Model
42
2.1 Synchronous Network Systems
42
2.2 Failures
44
2.3 Inputs and Outputs
45
2.4 Executions
45
2.5 Proof Methods
46
2.6 Complexity Measures
46
2.7 Randomization
47
2.8 Bibliographic Notes
48
Chapter 3. Leader Election in a Synchronous Ring
50
3.1 The Problem
50
3.2 Impossibility Result for Identical Processes
52
3.3 A Basic Algorithm
52
3.4 An Algorithm with O (n log n) Communication Complexity
56
3.5 Non-Comparison-Based Algorithms
60
3.6 Lower Bound for Comparison-Based Algorithms
63
3.7 Lower Bound for Non-Comparison-Based Algorithms
69
3.8 Bibliographic Notes
71
3.9 Exercises
72
Chapter 4. Algorithms in General Synchronous Networks
76
4.1 Leader Election in a General Network
77
4.2 Breadth-First Search
82
4.3 Shortest Paths
86
4.4 Minimum Spanning Tree
88
4.5 Maximal Independent Set
96
4.6 Bibliographic Notes
101
4.7 Exercises
102
Chapter 5. Distributed Consensus with Link Failures
106
5.1 The Coordinated Attack Problem—Deterministic Version
107
5.2 The Coordinated Attack Problem—Randomized Version
111
5.3 Bibliographic Notes
120
5.4 Exercises
120
Chapter 6. Distributed Consensus with Process Failures
124
6.1 The Problem
125
6.2 Algorithms for Stopping Failures
127
6.3 Algorithms for Byzantine Failures
141
6.4 Number of Processes for Byzantine Agreement
154
6.5 Byzantine Agreement in General Graphs
160
6.6 Weak Byzantine Agreement
164
6.7 Number of Rounds with Stopping Failures
167
6.8 Bibliographic Notes
177
6.9 Exercises
178
Chapter 7. More Consensus Problems
186
7.1 k-Agreement
186
7.2 Approximate Agreement
202
7.3 The Commit Problem
207
7.4 Bibliographic Notes
217
7.5 Exercises
217
Part II: Asynchronous Algorithms
222
Chapter 8. Modelling II: Asynchronous System Model
224
8.1 I/O Automata
225
8.2 Operations on Automata
231
8.3 Fairness
237
8.4 Inputs and Outputs for Problems
240
8.5 Properties and Proof Methods
241
8.6 Complexity Measures
253
8.7 Indistinguishable Executions
254
8.8 Randomization
254
8.9 Bibliographic Notes
255
8.10 Exercises
256
Part IIA: Asynchronous Shared Memory Algorithms
260
Chapter 9. Modelling III: Asynchronous Shared Memory Model
262
9.1 Shared Memory Systems
262
9.2 Environment Model
266
9.3 Indistinguishable States
269
9.4 Shared Variable Types
269
9.5 Complexity Measures
275
9.6 Failures
276
9.7 Randomization
276
9.8 Bibliographic Notes
276
9.9 Exercises
277
Chapter 10. Mutual Exclusion
280
10.1 Asynchronous Shared Memory Model
281
10.2 The Problem
284
10.3 Dijkstra's Mutual Exclusion Algorithm
290
10.4 Stronger Conditions for Mutual Exclusion Algorithms
301
10.5 Lockout-Free Mutual Exclusion Algorithms
303
10.6 An Algorithm Using Single-Writer Shared Registers
319
10.7 The Bakery Algorithm
321
10.8 Lower Bound on the Number of Registers
325
10.9 Mutual Exclusion Using Read-Modify-Write Shared Variables
334
10.10 Bibliographic Notes
351
10.11 Exercises
352
Chapter 11. Resource Allocation
360
11.1 The Problem
361
11.2 Nonexistence of Symmetric Dining Philosophers Algorithms
366
11.3 Right-Left Dining Philosophers Algorithm
369
11.4 Randomized Dining Philosophers Algorithm
379
11.5 Bibliographic Notes
392
11.6 Exercises
392
Chapter 12. Consensus
396
12.1 The Problem
397
12.2 Agreement Using Read/Write Shared Memory
401
12.3 Agreement Using Read-Modify-Write Shared Memory
412
12.4 Other Types of Shared Memory
413
12.5 Computability in Asynchronous Shared Memory Systems
414
12.6 Bibliographic Notes
416
12.7 Exercises
417
Chapter 13. Atomic Objects
422
13.1 Definitions and Basic Results
423
13.2 Implementing Read-Modify-Write Atomic Objects in Terms of Read/Write Variables
445
13.3 Atomic Snapshots of Shared Memory
446
13.4 Read/Write Atomic Objects
459
13.5 Bibliographic Notes
474
13.6 Exercises
475
Part IIB: Asynchronous Network Algorithms
480
Chapter 14. Modelling IV: Asynchronous Network Model
482
14.1 Send/Receive Systems
482
14.2 Broadcast Systems
491
14.3 Multicast Systems
494
14.4 Bibliographic Notes
496
14.5 Exercises
496
Chapter 15. Basic Asynchronous Network Algorithms
500
15.1 Leader Election in a Ring
500
15.2 Leader Election in an Arbitrary Network
520
15.3 Spanning Tree Construction, Broadcast and Convergecast
521
15.4 Breadth-First Search and Shortest Paths
526
15.5 Minimum Spanning Tree
534
15.6 Bibliographic Notes
548
15.7 Exercises
549
Chapter 16. Synchronizers
556
16.1 The Problem
557
16.2 The Local Synchronizer
560
16.3 The Safe Synchronizer
566
16.4 Safe Synchronizer Implementations
571
16.5 Applications
578
16.6 Lower Bound on Time
580
16.7 Bibliographic Notes
585
16.8 Exercises
585
Chapter 17. Shared Memory versus Networks
590
17.1 Transformations from the Shared Memory Model to the Network Model
591
17.2 Transformations from the Network Model to the Shared Memory Model
607
17.3 Bibliographic Notes
611
17.4 Exercises
612
Chapter 18. Logical Time
616
18.1 Logical Time for Asynchronous Networks
616
18.2 Adding Logical Time to Asynchronous Algorithms
621
18.3 Applications
625
18.4 Transforming Real-Time Algorithms to Logical-Time Algorithms
635
18.5 Bibliographic Notes
637
18.6 Exercises
637
Chapter 19. Consistent Global Snapshots and Stable Property Detection
642
19.1 Termination-Detection for Diffusing Algorithms
643
19.2 Consistent Global Snapshots
650
19.3 Bibliographic Notes
661
19.4 Exercises
662
Chapter 20. Network Resource Allocation
666
20.1 Mutual Exclusion
666
20.2 General Resource Allocation
678
20.3 Bibliographic Notes
689
20.4 Exercises
689
Chapter 21. Asynchronous Network Computing with Process Failures
694
21.1 The Network Model
695
21.2 Impossibility of Agreement in the Presence of Faults
696
21.3 A Randomized Algorithm
697
21.4 Failure Detectors
702
21.5 k-Agreement
706
21.6 Approximate Agreement
707
21.7 Computability in Asynchronous Networks
709
21.8 Bibliographic Notes
710
21.9 Exercises
711
Chapter 22. Data Link Protocols
716
22.1 The Problem
717
22.2 Stenning's Protocol
718
22.3 Alternating Bit Protocol
722
22.4 Bounded Tag Protocols Tolerating Reordering
728
22.5 Tolerating Crashes
740
22.6 Bibliographic Notes
753
22.7 Exercises
754
Part III: Partially Synchronous Algorithms
758
Chapter 23. Modelling V: Partially Synchronous System Models
760
23.1 MMT Timed Automata
761
23.2 General Timed Automata
769
23.3 Properties and Proof Methods
781
23.4 Modelling Shared Memory and Network Systems
793
23.5 Bibliographic Notes
794
23.6 Exercises
795
Chapter 24. Mutual Exclusion with Partial Synchrony
798
24.1 The Problem
798
24.2 A Single-Register Algorithm
799
24.3 Resilience to Timing Failures
809
24.4 Impossibility Results
813
24.5 Bibliographic Notes
815
24.6 Exercises
816
Chapter 25. Consensus with Partial Synchrony
820
25.1 The Problem
820
25.2 A Failure Detector
821
25.3 Basic Results
823
25.4 An Efficient Algorithm
828
25.5 A Lower Bound Involving the Timing Uncertainty
835
25.6 Other Results
843
25.7 Postscript
848
25.8 Bibliographic Notes
848
25.9 Exercises
849
Bibliography
854
Index
882
Related Titles from Morgan Kaufmann
898
Alle Preise verstehen sich inklusive der gesetzlichen MwSt.