Distributed Algorithms (eBook)

Nancy A. Lynch (Autor)

eBook Download: EPUB

1996 | 1. Auflage
904 Seiten
Elsevier Science (Verlag)
978-0-08-050470-4 (ISBN)

Infos

In Distributed Algorithms, Nancy Lynch provides a blueprint for designing, implementing, and analyzing distributed algorithms. She directs her book at a wide audience, including students, programmers, system designers, and researchers.

Distributed Algorithms contains the most significant algorithms and impossibility results in the area, all in a simple automata-theoretic setting. The algorithms are proved correct, and their complexity is analyzed according to precisely defined complexity measures. The problems covered include resource allocation, communication, consensus among distributed processes, data consistency, deadlock detection, leader election, global snapshots, and many others.

The material is organized according to the system model-first by the timing model and then by the interprocess communication mechanism. The material on system models is isolated in separate chapters for easy reference.

The presentation is completely rigorous, yet is intuitive enough for immediate comprehension. This book familiarizes readers with important problems, algorithms, and impossibility results in the area: readers can then recognize the problems when they arise in practice, apply the algorithms to solve them, and use the impossibility results to determine whether problems are unsolvable. The book also provides readers with the basic mathematical tools for designing new algorithms and proving new impossibility results. In addition, it teaches readers how to reason carefully about distributed algorithms-to model them formally, devise precise specifications for their required behavior, prove their correctness, and evaluate their performance with realistic measures.

Inhalt

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

Produkt-Details

• Erscheint lt. Verlag: 16.4.1996
• Sprache: englisch
• Themenwelt: Mathematik / Informatik ► Informatik ► Datenbanken
• Themenwelt: Mathematik / Informatik ► Informatik ► Netzwerke
• Themenwelt: Informatik ► Theorie / Studium ► Kryptologie
• Themenwelt: Sozialwissenschaften ► Kommunikation / Medien ► Buchhandel / Bibliothekswesen
• Themenwelt: Technik ► Fahrzeugbau / Schiffbau
• Themenwelt: Technik ► Luft- / Raumfahrttechnik
• ISBN-10: 0-08-050470-1 / 0080504701
• ISBN-13: 978-0-08-050470-4 / 9780080504704