Distributed Algorithms, Second
An Intuitive Approach
by Fokkink
ISBN: 9780262364621  Copyright 2018
Instructor Requests
The new edition of a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models.
This book offers students and researchers a guide to distributed algorithms that emphasizes examples and exercises rather than the intricacies of mathematical models. It avoids mathematical argumentation, often a stumbling block for students, teaching algorithmic thought rather than proofs and logic. This approach allows the student to learn a large number of algorithms within a relatively short span of time. Algorithms are explained through brief, informal descriptions, illuminating examples, and practical exercises. The examples and exercises allow readers to understand algorithms intuitively and from different perspectives. Proof sketches, arguing the correctness of an algorithm or explaining the idea behind fundamental results, are also included. The algorithms presented in the book are for the most part “classics,” selected because they shed light on the algorithmic design of distributed systems or on key issues in distributed computing and concurrent programming.
This second edition has been substantially revised. A new chapter on distributed transaction offers uptodate treatment of database transactions and the important evolving area of transactional memory. A new chapter on security discusses two exciting new topics: blockchains and quantum cryptography. Sections have been added that cover such subjects as rollback recovery, faulttolerant termination detection, and consensus for shared memory. An appendix offers pseudocode descriptions of many algorithms. Solutions and slides are available for instructors.
Distributed Algorithms can be used in courses for upperlevel undergraduates or graduate students in computer science, or as a reference for researchers in the field.
Expand/Collapse All  

Contents (pg. v)  
Preface (pg. xi)  
1. Introduction (pg. 1)  
2. Preliminaries (pg. 3)  
2.1 Mathematical Notions (pg. 3)  
2.2 Message Passing (pg. 5)  
2.3 Shared Memory (pg. 10)  
2.4 Exercises (pg. 12)  
3. Snapshots (pg. 15)  
3.1 ChandyLamport Algorithm (pg. 16)  
3.2 LaiYang Algorithm (pg. 17)  
3.3 PetersonKearns Rollback Recovery Algorithm (pg. 18)  
3.4 Exercises (pg. 21)  
4. Waves (pg. 23)  
4.1 Traversal Algorithms (pg. 23)  
4.2 Tree Algorithm (pg. 26)  
4.3 Echo Algorithm (pg. 28)  
4.4 Exercises (pg. 29)  
5. Deadlock Detection (pg. 31)  
5.1 Waitfor Graphs (pg. 31)  
5.2 BrachaToueg Algorithm (pg. 32)  
5.3 Exercises (pg. 39)  
6. Termination Detection (pg. 41)  
6.1 DijkstraScholten Algorithm (pg. 42)  
6.2 Rana’s Algorithm (pg. 43)  
6.3 Safra’s Algorithm (pg. 45)  
6.4 Weight Throwing (pg. 46)  
6.5 FaultTolerant Weight Throwing (pg. 47)  
6.6 Exercises (pg. 49)  
7. Garbage Collection (pg. 51)  
7.1 Reference Counting (pg. 51)  
7.2 Garbage Collection Implies Termination Detection� (pg. 54)  
7.3 Tracing (pg. 54)  
7.4 Exercises (pg. 55)  
8. Routing (pg. 57)  
8.1 ChandyMisra Algorithm (pg. 57)  
8.2 MerlinSegall Algorithm (pg. 59)  
8.3 Toueg’s Algorithm (pg. 62)  
8.4 Frederickson’s Algorithm (pg. 64)  
8.5 Packet Switching (pg. 68)  
8.6 Routing on the Internet (pg. 70)  
8.7 Exercises (pg. 71)  
9. Election (pg. 75)  
9.1 Election in Rings (pg. 75)  
9.2 Tree Election Algorithm (pg. 79)  
9.3 Echo Algorithm with Extinction (pg. 80)  
9.4 Minimum Spanning Trees (pg. 81)  
9.5 Exercises (pg. 86)  
10. Anonymous Networks (pg. 89)  
10.1 Impossibility of Election in Anonymous Rings&# (pg. 89)  
10.2 Probabilistic Algorithms (pg. 90)  
10.3 ItaiRodeh Election Algorithm for Rings (pg. 91)  
10.4 Echo Algorithm with Extinction for Anonymous Networks& (pg. 92)  
10.5 Computing the Size of an Anonymous Ring Is Impossible& (pg. 94)  
10.6 ItaiRodeh Ring Size Algorithm (pg. 95)  
10.7 Election in IEEE 1394 (pg. 97)  
10.8 Exercises (pg. 98)  
11. Synchronous Networks (pg. 101)  
11.1 Awerbuch’s Synchronizer (pg. 101)  
11.2 Bounded Delay Networks with Local Clocks (pg. 104)  
11.3 Election in Anonymous Rings with Bounded Expected Delay� (pg. 105)  
11.4 Exercises (pg. 108)  
12. Consensus with Crash Failures (pg. 109)  
12.1 Impossibility of 1Crash Consensus (pg. 110)  
12.2 BrachaToueg Crash Consensus Algorithm (pg. 111)  
12.3 Failure Detectors (pg. 113)  
12.4 Consensus with a Weakly Accurate Failure Detector& (pg. 114)  
12.5 ChandraToueg Algorithm (pg. 114)  
12.6 Consensus for Shared Memory (pg. 117)  
12.7 Exercises (pg. 118)  
13. Consensus with Byzantine Failures (pg. 121)  
13.1 BrachaToueg Byzantine Consensus Algorithm (pg. 121)  
13.2 MahaneySchneider Synchronizer (pg. 125)  
13.3 LamportShostakPease Broadcast Algorithm& (pg. 127)  
13.4 LamportShostakPease Authentication Algorithm (pg. 130)  
13.5 Exercises (pg. 131)  
14. Mutual Exclusion (pg. 135)  
14.1 RicartAgrawala Algorithm (pg. 136)  
14.2 Raymond’s Algorithm (pg. 137)  
14.3 Agrawal–El Abbadi Algorithm (pg. 140)  
14.4 Peterson’s Algorithm (pg. 142)  
14.5 Bakery Algorithm (pg. 145)  
14.6 Fischer’s Algorithm (pg. 147)  
14.7 TestandTestandSet Lock (pg. 148)  
14.8 Queue Locks (pg. 149)  
14.9 Exercises (pg. 153)  
15. Barriers (pg. 157)  
15.1 SenseReversing Barrier (pg. 157)  
15.2 Combining Tree Barrier (pg. 158)  
15.3 Tournament Barrier (pg. 161)  
15.4 Dissemination Barrier (pg. 163)  
15.5 Exercises (pg. 165)  
16. Distributed Transactions (pg. 167)  
16.1 Serialization (pg. 168)  
16.2 Two and ThreePhase Commit Protocols (pg. 171)  
16.3 Transactional Memory (pg. 173)  
16.4 Exercises (pg. 176)  
17. SelfStabilization (pg. 177)  
17.1 Dijkstra’s Token Ring for Mutual Exclusion (pg. 177)  
17.2 AroraGouda Spanning Tree Algorithm (pg. 180)  
17.3 AfekKuttenYung Spanning Tree Algorithm (pg. 183)  
17.4 Exercises (pg. 185)  
18. Security (pg. 187)  
18.1 Basic Techniques (pg. 187)  
18.2 Blockchains (pg. 191)  
18.3 Quantum Cryptography (pg. 194)  
18.4 Exercises (pg. 198)  
19. Online Scheduling (pg. 201)  
19.1 Jobs (pg. 201)  
19.2 Schedulers (pg. 202)  
19.3 Resource Access Control (pg. 207)  
19.4 Exercises (pg. 209)  
A. Appendix: Pseudocode Descriptions (pg. 211)  
A.1 ChandyLamport Snapshot Algorithm (pg. 212)  
A.2 LaiYang Snapshot Algorithm (pg. 212)  
A.3 Cidon’s DepthFirst Search Algorithm (pg. 214)  
A.4 Tree Algorithm (pg. 215)  
A.5 Echo Algorithm (pg. 215)  
A.6 ShavitFrancez Termination Detection Algorithm& (pg. 216)  
A.7 Rana’s Termination Detection Algorithm (pg. 217)  
A.8 Safra’s Termination Detection Algorithm (pg. 218)  
A.9 WeightThrowing Termination Detection Algorithm (pg. 219)  
A.10 ChandyMisra Routing Algorithm (pg. 220)  
A.11 MerlinSegall Routing Algorithm (pg. 221)  
A.12 Toueg’s Routing Algorithm (pg. 222)  
A.13 Frederickson’s BreadthFirst Search Algorithm& (pg. 223)  
A.14 DolevKlaweRodeh Election Algorithm (pg. 225)  
A.15 GallagerHumbletSpira Minimum Spanning Tree Algorithm (pg. 226)  
A.16 IEEE 1394 Election Algorithm (pg. 229)  
A.17 Awerbuch’s Synchronizer (pg. 230)  
A.18 RicartAgrawala Mutual Exclusion Algorithm (pg. 231)  
A.19 Raymond’s Mutual Exclusion Algorithm (pg. 232)  
A.20 Agrawal–El Abbadi Mutual Exclusion Algorithm&# (pg. 234)  
A.21 MCS Queue Lock (pg. 235)  
A.22 CLH Queue Lock with Timeouts (pg. 236)  
A.23 AfekKuttenYung Spanning Tree Algorithm (pg. 237)  
References (pg. 241)  
Index (pg. 247) 
Wan Fokkink
Wan Fokkink is Professor of Theoretical Computer Science at the VU University, Amsterdam, and Professor of Stochastics Design at Eindhoven University for Technology.
Instructors  

You must have an instructor account and submit a request to access instructor materials for this book.

eTextbook
Go paperless today! Available online anytime, nothing to download or install.
Features
