Principles of Distributed Computing

Description

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