Principles of Distributed Computing

Title......Page 1
Contents......Page 3
What is Distributed Computing?......Page 7
Course Overview......Page 8
Bibliography......Page 9
1.1. Problem & Model......Page 11
1.2. Coloring Trees......Page 14
Bibliography......Page 18
2.1. Broadcast......Page 21
2.2. Convergecast......Page 23
2.3. BFS Tree Construction......Page 24
2.4. MST Construction......Page 25
Chapter Notes......Page 27
Bibliography......Page 28
3.1. Anonymous Leader Election......Page 29
3.2. Anonymous Ring......Page 30
3.3. Lower Bounds......Page 32
3.4. Synchronous Ring......Page 35
Bibliography......Page 36
4.1. Array & Mesh......Page 39
4.2. Sorting Networks......Page 42
4.3. Counting Networks......Page 45
Chapter Notes......Page 49
Bibliography......Page 50
5.1. Model......Page 53
5.2. Mutual Exclusion......Page 54
5.3.1. Problem Definition......Page 57
5.3.2. Splitters......Page 58
5.3.3. Binary Splitter Tree......Page 59
5.3.4. Splitter Matrix......Page 61
Bibliography......Page 62
6.1. Centralized Solutions......Page 65
6.2. Arrow and Friends......Page 66
6.3. Ivy and Friends......Page 71
Bibliography......Page 74
7.1. MIS......Page 77
7.2. Original Fast MIS......Page 79
7.3. Fast MIS v2......Page 82
7.4. Applications......Page 86
Chapter Notes......Page 87
Bibliography......Page 88
8.1. Model......Page 91
8.2. Locality......Page 92
8.3. The Neighborhood Graph......Page 94
Chapter Notes......Page 97
Bibliography......Page 98
9. Social Networks......Page 99
9.1. Small World Networks......Page 100
9.2. Propogation Studies......Page 106
Bibliography......Page 108
10.1. Basics......Page 111
10.2. The Local Synchronizer Alpha......Page 112
10.3. The Global Synchronizer Beta......Page 113
10.4. The Hybrid Synchronizer Gamma......Page 114
10.5. Network Partition......Page 116
10.6. Clock Synchronization......Page 118
Bibliography......Page 120
11.1. Diameter & APSP......Page 125
11.2. Lower Bound Graphs......Page 127
11.3. Communication Complexity......Page 130
11.4. Distributed Complexity Theory......Page 135
Bibliography......Page 136
12.1. Basics......Page 139
12.2.2. Uniform Initialization with CD......Page 141
12.3.1. With High Probability......Page 143
12.3.2. Uniform Leader Election......Page 144
12.3.4. Even Faster Leader Election with CD......Page 145
12.3.6. Uniform Asynchronous Wakeup without CD......Page 148
12.4. Useful Formulas......Page 149
Bibliography......Page 150
13.1. Self-Stabilization......Page 153
13.2. Advanced Stabilization......Page 158
Chapter Notes......Page 160
Bibliography......Page 161
14.1. Adjacency......Page 163
14.2. Rooted Trees......Page 165
14.3. Road Networks......Page 166
Chapter Notes......Page 168
Bibliography......Page 169
15.1. Client/Server......Page 171
15.2. Paxos......Page 175
Chapter Notes......Page 180
Bibliography......Page 181
16.2. Consensus......Page 183
16.3. Impossibility of Consensus......Page 184
16.4. Randomized Consensus......Page 189
16.5. Shared Coin......Page 192
Chapter Notes......Page 193
Bibliography......Page 194
17. Byzantine Agreement......Page 195
17.1. Validity......Page 196
17.2. How Many Byzantine Nodes?......Page 197
17.3. The King Algorithms......Page 199
17.4. Lower Bound on Number of Rounds......Page 200
17.5. Asynchronous Byzantine Agreement......Page 201
Chapter Notes......Page 202
Bibliography......Page 203
18.1. Agreement with Authentication......Page 205
18.2. Zyzzyva......Page 207
Chapter Notes......Page 215
Bibliography......Page 216
19. Quorum Systems......Page 217
19.1. Load and Work......Page 218
19.2. Grid Quorum Systems......Page 219
19.3. Fault Tolerance......Page 221
19.4. Byzantine Quorum Systems......Page 224
Bibliography......Page 227
20.1. Consistency, Availability and Partitions......Page 229
20.2. Bitcoin......Page 231
20.3. Smart Contracts......Page 237
20.4. Weak Consistency......Page 239
Chapter Notes......Page 240
Bibliography......Page 241
20.1. Consistent Hashing......Page 243
20.2. Hypercubic Networks......Page 244
20.3. DHT & Churn......Page 250
Chapter Notes......Page 253
Bibliography......Page 254
22.2. Prisoner's Dilemma......Page 257
22.3. Selfish Caching......Page 259
22.4. Braess' Paradox......Page 261
22.5. Rock-Paper-Scissors......Page 262
22.6. Mechanism Design......Page 263
Chapter Notes......Page 265
Bibliography......Page 266
23.1. Synchronous Edge-Dynamic Networks......Page 267
23.2. Problem Definitions......Page 268
23.3. Basic Information Dissemination......Page 269
23.4.1. k-Verification......Page 272
23.4.2. k-Committee Election......Page 273
23.5 More Stable Graphs......Page 275
Bibliography......Page 278
24. All-to-All Communication......Page 279
Chapter Notes......Page 283
Bibliography......Page 284
25.1.1. The Current State of Concurrent Programming......Page 287
25.2. Transaction Memory......Page 289
25.3. Contention Management......Page 290
Bibliography......Page 296
26. Dominating Set......Page 299
26.1. Sequential Greedy Algorithm......Page 300
26.2. Distributed Greedy Algorithm......Page 301
Chapter Notes......Page 306
Bibliography......Page 307
27.1. Array......Page 309
27.2. Mesh......Page 310
27.3. Routing in the Mesh with Small Queues......Page 311
27.4. Hot-Potato Routing......Page 312
Bibliography......Page 314
28.1. Butterfly......Page 317
28.2. Oblivious Routing......Page 318
28.3. Offline Routing......Page 319
Bibliography......Page 321