Table of Contents
Preface xi
1 Introduction 1
2 Preliminaries 3
2.1 Mathematical Notions 3
2.2 Message Passing 5
2.3 Shared Memory 10
2.4 Exercises 12
3 Snapshots 15
3.1 Chandy-Lamport Algorithm 16
3.2 Lai-Yang Algorithm 17
3.3 Peterson-Kearns Rollback Recovery Algorithm 18
3.4 Exercises 21
4 Waves 23
4.1 Traversal Algorithms 23
4.2 Tree Algorithm 26
4.3 Echo Algorithm 28
4.4 Exercises 29
5 Deadlock Detection 31
5.1 Wait-for Graphs 31
5.2 Bracha-Toueg Algorithm 32
5.3 Exercises 39
6 Termination Detection 41
6.1 Dijkstra-Scholten Algorithm 42
6.2 Rana's Algorithm 43
6.3 Safra's Algorithm 45
6.4 Weight Throwing 46
6.5 Fault-Tolerant Weight Throwing 47
6.6 Exercises 49
7 Garbage Collection 51
7.1 Reference Counting 51
7.2 Garbage Collection Implies Termination Detection 54
7.3 Tracing 54
7.4 Exercises 55
8 Routing 57
8.1 Chandy-Misra Algorithm 57
8.2 Merlin-Segall Algorithm 59
8.3 Toueg's Algorithm 62
8.4 Frederickson's Algorithm 64
8.5 Packet Switching 68
8.6 Routing on the Internet 70
8.7 Exercises 71
9 Election 75
9.1 Election in Rings 75
9.2 Tree Election Algorithm 79
9.3 Echo Algorithm with Extinction 80
9.4 Minimum Spanning Trees 81
9.5 Exercises 86
10 Anonymous Networks 89
10.1 Impossibility of Election in Anonymous Rings 89
10.2 Probabilistic Algorithms 90
10.3 Itai-Rodeh Election Algorithm for Rings 91
10.4 Echo Algorithm with Extinction for Anonymous Networks 92
10.5 Computing the Size of an Anonymous Ring Is Impossible 94
10.6 Itai-Rodeh Ring Size Algorithm 95
10.7 Election in IEEE 1394 97
10.8 Exercises 98
11 Synchronous Networks 101
11.1 Awerbuch's Synchronizer 101
11.2 Bounded Delay Networks with Local Clocks 104
11.3 Election in Anonymous Rings with Bounded Expected Delay 105
11.4 Exercises 108
12 Consensus with Crash Failures 109
12.1 Impossibility of 1-Crash Consensus 110
12.2 Bracha-Toueg Crash Consensus Algorithm 111
12.3 Failure Detectors 113
12.4 Consensus with a Weakly Accurate Failure Detector 114
12.5 Chandra-Toueg Algorithm 114
12.6 Consensus for Shared Memory 117
12.7 Exercises 118
13 Consensus with Byzantine Failures 121
13.1 Bracha-Toueg Byzantine Consensus Algorithm 121
13.2 Mahaney-Schneider Synchronizer 125
13.3 Lamport-Shostak-Pease Broadcast Algorithm 127
13.4 Lamport-Shostak-Pease Authentication Algorithm 130
13.5 Exercises 132
14 Mutual Exclusion 135
14.1 Ricart-Agrawala Algorithm 136
14.2 Raymond's Algorithm 137
14.3 Agrawal-El Abbadi Algorithm 140
14.4 Peterson's Algorithm 142
14.5 Bakery Algorithm 145
14.6 Fischer's Algorithm 147
14.7 Test-and-Test-and-Set Lock 148
14.8 Queue Locks 149
14.9 Exercises 153
15 Barriers 157
15.1 Sense-Reversing Barrier 157
15.2 Combining Tree Barrier 158
15.3 Tournament Barrier 161
15.4 Dissemination Barrier 163
15.5 Exercises 165
16 Distributed Transactions 167
16.1 Serialization 168
16.2 Two- and Three-Phase Commit Protocols 171
16.3 Transactional Memory 173
16.4 Exercises 176
17 Self-Stabilization 177
17.1 Dijkstra's Token Ring for Mutual Exclusion 177
17.2 Arora-Gouda Spanning Tree Algorithm 180
17.3 Afek-Kutten-Yung Spanning Tree Algorithm 183
17.4 Exercises 185
18 Security 187
18.1 Basic Techniques 187
18.2 Blockchains 191
18.3 Quantum Cryptography 194
18.4 Exercises 198
19 Online Scheduling 201
19.1 Jobs 201
19.2 Schedulers 202
19.3 Resource Access Control 207
19.4 Exercises 209
A Appendix: Pseudocode Descriptions 211
A.1 Chandy-Lamport Snapshot Algorithm 212
A.2 Lai-Yang Snapshot Algorithm 212
A.3 Cidon's Depth-First Search Algorithm 214
A.4 Tree Algorithm 215
A.5 Echo Algorithm 215
A.6 Shavit-Francez Termination Detection Algorithm 216
A.7 Rana's Termination Detection Algorithm 217
A.8 Safra's Termination Detection Algorithm 218
A.9 Weight-Throwing Termination Detection Algorithm 219
A.10 Chandy-Misra Routing Algorithm 220
A.11 Merlin-Segall Routing Algorithm 221
A.12 Toueg's Routing Algorithm 222
A.13 Frederickson's Breadth-First Search Algorithm 223
A.14 Dolev-Klawe-Rodeh Election Algorithm 225
A.15 Gallager-Humblet-Spira Minimum Spanning Tree Algorithm 226
A.16 IEEE 1394 Election Algorithm 229
A.17 Awerbuch's Synchronizer 230
A.18 Ricart-Agrawala Mutual Exclusion Algorithm 231
A.19 Raymond's Mutual Exclusion Algorithm 232
A.20 Agrawal-El Abbadi Mutual Exclusion Algorithm 234
A.21 MCS Queue Lock 235
A.22 CLH Queue Lock with Timeouts 236
A.23 Afek-Kutten-Yung Spanning Tree Algorithm 237
References 241
Index 247
