Lecture Notes on Theory of Distributed Systems

theory and implementation aspects of distributed operating systems and applied optimal control theory of distributed systems pdf free download
Dr.JamesSmith Profile Pic
Dr.JamesSmith,France,Professional
Published Date:11-07-2017
Your Website URL(Optional)
Comment
Notes on Theory of Distributed Systems CPSC 465/565: Fall 2017 James Aspnes 2017-05-15 15:58Contents Table of contents i List of figures xiii List of tables xiv List of algorithms xv Preface xix Syllabus xxi Lecture schedule xxiv 1 Introduction 1 1.1 Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 I Message passing 7 2 Model 9 2.1 Basic message-passing model . . . . . . . . . . . . . . . . . . 9 2.1.1 Formal details . . . . . . . . . . . . . . . . . . . . . . 10 2.1.2 Network structure . . . . . . . . . . . . . . . . . . . . 11 2.2 Asynchronous systems . . . . . . . . . . . . . . . . . . . . . . 11 2.2.1 Example: client-server computing . . . . . . . . . . . . 12 2.3 Synchronous systems . . . . . . . . . . . . . . . . . . . . . . . 13 2.4 Drawing message-passing executions . . . . . . . . . . . . . . 13 2.5 Complexity measures . . . . . . . . . . . . . . . . . . . . . . . 15 iCONTENTS ii 3 Coordinated attack 17 3.1 Formal description . . . . . . . . . . . . . . . . . . . . . . . . 17 3.2 Impossibility proof . . . . . . . . . . . . . . . . . . . . . . . . 18 3.3 Randomized coordinated attack . . . . . . . . . . . . . . . . . 19 3.3.1 An algorithm . . . . . . . . . . . . . . . . . . . . . . . 20 3.3.2 Why it works . . . . . . . . . . . . . . . . . . . . . . . 21 3.3.3 Almost-matching lower bound . . . . . . . . . . . . . . 22 4 Broadcast and convergecast 23 4.1 Flooding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 4.1.1 Basic algorithm . . . . . . . . . . . . . . . . . . . . . . 23 4.1.2 Adding parent pointers . . . . . . . . . . . . . . . . . 25 4.1.3 Termination . . . . . . . . . . . . . . . . . . . . . . . . 26 4.2 Convergecast . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.3 Flooding and convergecast together . . . . . . . . . . . . . . . 28 5 Distributed breadth-first search 30 5.1 Using explicit distances . . . . . . . . . . . . . . . . . . . . . 30 5.2 Using layering . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 5.3 Using local synchronization . . . . . . . . . . . . . . . . . . . 32 6 Leader election 36 6.1 Symmetry . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 6.2 Leader election in rings . . . . . . . . . . . . . . . . . . . . . 38 6.2.1 The Le-Lann-Chang-Roberts algorithm . . . . . . . . 38 6.2.1.1 Proof of correctness for synchronous executions 39 6.2.1.2 Performance . . . . . . . . . . . . . . . . . . 39 6.2.2 The Hirschberg-Sinclair algorithm . . . . . . . . . . . 40 6.2.3 Peterson’s algorithm for the unidirectional ring . . . . 41 6.2.4 A simple randomized O(n logn)-message algorithm . . 43 6.3 Leader election in general networks . . . . . . . . . . . . . . . 43 6.4 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 6.4.1 Lower bound on asynchronous message complexity . . 44 6.4.2 Lower bound for comparison-based algorithms . . . . 45 7 Logical clocks 48 7.1 Causal ordering . . . . . . . . . . . . . . . . . . . . . . . . . . 48 7.2 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . 50 7.2.1 Lamport clock . . . . . . . . . . . . . . . . . . . . . . 51 7.2.2 Neiger-Toueg-Welch clock . . . . . . . . . . . . . . . . 51CONTENTS iii 7.2.3 Vector clocks . . . . . . . . . . . . . . . . . . . . . . . 52 7.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 7.3.1 Consistent snapshots . . . . . . . . . . . . . . . . . . . 53 7.3.1.1 Property testing . . . . . . . . . . . . . . . . 54 8 Synchronizers 56 8.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 8.2 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . 57 8.2.1 The alpha synchronizer . . . . . . . . . . . . . . . . . 58 8.2.2 The beta synchronizer . . . . . . . . . . . . . . . . . . 58 8.2.3 The gamma synchronizer . . . . . . . . . . . . . . . . 59 8.3 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 8.4 Limitations of synchronizers . . . . . . . . . . . . . . . . . . . 60 8.4.1 Impossibility with crash failures . . . . . . . . . . . . 60 8.4.2 Unavoidable slowdown with global synchronization . . 61 9 Synchronous agreement 63 9.1 Problem definition . . . . . . . . . . . . . . . . . . . . . . . . 63 9.2 Solution using flooding . . . . . . . . . . . . . . . . . . . . . . 64 9.3 Lower bound on rounds . . . . . . . . . . . . . . . . . . . . . 65 9.4 Variants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 10 Byzantine agreement 69 10.1 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 10.1.1 Minimum number of rounds . . . . . . . . . . . . . . . 69 10.1.2 Minimum number of processes . . . . . . . . . . . . . 69 10.1.3 Minimum connectivity . . . . . . . . . . . . . . . . . . 71 10.1.4 Weak Byzantine agreement . . . . . . . . . . . . . . . 72 10.2 Upper bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 10.2.1 Exponential information gathering gets n = 3f + 1 . . 74 10.2.1.1 Proof of correctness . . . . . . . . . . . . . . 75 10.2.2 Phase king gets constant-size messages . . . . . . . . . 77 10.2.2.1 The algorithm . . . . . . . . . . . . . . . . . 77 10.2.2.2 Proof of correctness . . . . . . . . . . . . . . 77 10.2.2.3 Performance of phase king . . . . . . . . . . 79 11 Impossibility of asynchronous agreement 80 11.1 Agreement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 11.2 Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 11.3 Steps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81CONTENTS iv 11.4 Bivalence and univalence . . . . . . . . . . . . . . . . . . . . . 82 11.5 Existence of an initial bivalent configuration . . . . . . . . . . 82 11.6 Staying in a bivalent configuration . . . . . . . . . . . . . . . 83 11.7 Generalization to other models . . . . . . . . . . . . . . . . . 84 12 Paxos 85 12.1 The Paxos algorithm . . . . . . . . . . . . . . . . . . . . . . . 85 12.2 Informal analysis: how information flows between rounds . . 87 12.2.1 Example execution . . . . . . . . . . . . . . . . . . . . 88 12.2.2 Safety properties . . . . . . . . . . . . . . . . . . . . . 88 12.2.3 Learning the results . . . . . . . . . . . . . . . . . . . 90 12.2.4 Liveness properties . . . . . . . . . . . . . . . . . . . . 91 12.3 Replicated state machines and multi-Paxos . . . . . . . . . . 91 13 Failure detectors 93 13.1 How to build a failure detector . . . . . . . . . . . . . . . . . 94 13.2 Classification of failure detectors . . . . . . . . . . . . . . . . 94 13.2.1 Degrees of completeness . . . . . . . . . . . . . . . . . 94 13.2.2 Degrees of accuracy . . . . . . . . . . . . . . . . . . . 94 13.2.3 Boosting completeness . . . . . . . . . . . . . . . . . . 95 13.2.4 Failure detector classes . . . . . . . . . . . . . . . . . . 96 13.3 Consensus with S . . . . . . . . . . . . . . . . . . . . . . . . . 97 13.3.1 Proof of correctness . . . . . . . . . . . . . . . . . . . 98 13.4 Consensus with S and f n/2 . . . . . . . . . . . . . . . . 99 13.4.1 Proof of correctness . . . . . . . . . . . . . . . . . . . 101 13.5 f n/2 is still required even with P . . . . . . . . . . . . . 102 13.6 Relationships among the classes . . . . . . . . . . . . . . . . . 102 14 Quorum systems 104 14.1 Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 14.2 Simple quorum systems . . . . . . . . . . . . . . . . . . . . . 104 14.3 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105 14.4 Paths system . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 14.5 Byzantine quorum systems . . . . . . . . . . . . . . . . . . . 107 14.6 Probabilistic quorum systems . . . . . . . . . . . . . . . . . . 108 14.6.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 109 14.6.2 Performance . . . . . . . . . . . . . . . . . . . . . . . 109 14.7 Signed quorum systems . . . . . . . . . . . . . . . . . . . . . 110CONTENTS v II Shared memory 111 15 Model 113 15.1 Atomic registers . . . . . . . . . . . . . . . . . . . . . . . . . 113 15.2 Single-writer versus multi-writer registers . . . . . . . . . . . 114 15.3 Fairness and crashes . . . . . . . . . . . . . . . . . . . . . . . 115 15.4 Concurrent executions . . . . . . . . . . . . . . . . . . . . . . 115 15.5 Consistency properties . . . . . . . . . . . . . . . . . . . . . . 116 15.6 Complexity measures . . . . . . . . . . . . . . . . . . . . . . . 117 15.7 Fancier registers . . . . . . . . . . . . . . . . . . . . . . . . . 118 16 Distributed shared memory 120 16.1 Message passing from shared memory . . . . . . . . . . . . . 121 16.2 The Attiya-Bar-Noy-Dolev algorithm . . . . . . . . . . . . . . 121 16.3 Proof of linearizability . . . . . . . . . . . . . . . . . . . . . . 123 16.4 Proof that f n/2 is necessary . . . . . . . . . . . . . . . . . 124 16.5 Multiple writers . . . . . . . . . . . . . . . . . . . . . . . . . . 124 16.6 Other operations . . . . . . . . . . . . . . . . . . . . . . . . . 125 17 Mutual exclusion 126 17.1 The problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 126 17.2 Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127 17.3 Mutual exclusion using strong primitives . . . . . . . . . . . . 127 17.3.1 Test and set . . . . . . . . . . . . . . . . . . . . . . . . 128 17.3.2 A lockout-free algorithm using an atomic queue . . . . 129 17.3.2.1 Reducing space complexity . . . . . . . . . . 130 17.4 Mutual exclusion using only atomic registers . . . . . . . . . 130 17.4.1 Peterson’s tournament algorithm . . . . . . . . . . . . 130 17.4.1.1 Correctness of Peterson’s protocol . . . . . . 132 17.4.1.2 Generalization to n processes . . . . . . . . . 134 17.4.2 Fast mutual exclusion . . . . . . . . . . . . . . . . . . 135 17.4.3 Lamport’s Bakery algorithm . . . . . . . . . . . . . . 137 17.4.4 Lower bound on the number of registers . . . . . . . . 139 17.5 RMR complexity . . . . . . . . . . . . . . . . . . . . . . . . . 141 17.5.1 Cache-coherence vs. distributed shared memory . . . . 141 17.5.2 RMR complexity of Peterson’s algorithm . . . . . . . 142 17.5.3 Mutual exclusion in the DSM model . . . . . . . . . . 143 17.5.4 Lower bounds . . . . . . . . . . . . . . . . . . . . . . . 145CONTENTS vi 18 The wait-free hierarchy 146 18.1 Classification by consensus number . . . . . . . . . . . . . . . 147 18.1.1 Level 1: registers etc. . . . . . . . . . . . . . . . . . . 148 18.1.2 Level 2: interfering RMW objects etc. . . . . . . . . . 150 18.1.3 Level∞: objects where the first write wins . . . . . . 151 18.1.4 Level 2m− 2: simultaneous m-register write . . . . . . 153 18.1.4.1 Matching impossibility result . . . . . . . . . 154 18.1.5 Level m: m-process consensus objects . . . . . . . . . 155 18.2 Universality of consensus . . . . . . . . . . . . . . . . . . . . . 156 19 Atomic snapshots 159 19.1 The basic trick: two identical collects equals a snapshot . . . 159 19.2 The Gang of Six algorithm . . . . . . . . . . . . . . . . . . . 160 19.2.1 Linearizability . . . . . . . . . . . . . . . . . . . . . . 161 19.2.2 Using bounded registers . . . . . . . . . . . . . . . . . 162 19.3 Faster snapshots using lattice agreement . . . . . . . . . . . . 165 19.3.1 Lattice agreement . . . . . . . . . . . . . . . . . . . . 165 19.3.2 Connection to vector clocks . . . . . . . . . . . . . . . 166 19.3.3 The full reduction . . . . . . . . . . . . . . . . . . . . 166 19.3.4 Why this works . . . . . . . . . . . . . . . . . . . . . . 167 19.3.5 Implementing lattice agreement . . . . . . . . . . . . . 169 19.4 Practical snapshots using LL/SC . . . . . . . . . . . . . . . . 172 19.4.1 Details of the single-scanner snapshot . . . . . . . . . 173 19.4.2 Extension to multiple scanners . . . . . . . . . . . . . 175 19.5 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176 19.5.1 Multi-writer registers from single-writer registers . . . 176 19.5.2 Counters and accumulators . . . . . . . . . . . . . . . 176 19.5.3 Resilient snapshot objects . . . . . . . . . . . . . . . . 177 20 Lower bounds on perturbable objects 178 21 Restricted-use objects 182 21.1 Implementing bounded max registers . . . . . . . . . . . . . . 182 21.2 Encoding the set of values . . . . . . . . . . . . . . . . . . . . 184 21.3 Unbounded max registers . . . . . . . . . . . . . . . . . . . . 185 21.4 Lower bound . . . . . . . . . . . . . . . . . . . . . . . . . . . 185 21.5 Max-register snapshots . . . . . . . . . . . . . . . . . . . . . . 187 21.5.1 Linearizability . . . . . . . . . . . . . . . . . . . . . . 189 21.5.2 Application to standard snapshots . . . . . . . . . . . 189CONTENTS vii 22 Common2 192 22.1 Test-and-set and swap for two processes . . . . . . . . . . . . 193 22.2 Building n-process TAS from 2-process TAS . . . . . . . . . . 194 22.3 Obstruction-free swap from test-and-set . . . . . . . . . . . . 195 22.4 Wait-free swap from test-and-set . . . . . . . . . . . . . . . . 197 23 Randomized consensus and test-and-set 201 23.1 Role of the adversary in randomized algorithms . . . . . . . . 201 23.2 History . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 23.3 Reduction to simpler primitives . . . . . . . . . . . . . . . . . 203 23.3.1 Adopt-commit objects . . . . . . . . . . . . . . . . . . 204 23.3.2 Conciliators . . . . . . . . . . . . . . . . . . . . . . . . 205 23.4 Implementing an adopt-commit object . . . . . . . . . . . . . 205 23.5 Conciliators and shared coins . . . . . . . . . . . . . . . . . . 206 23.6 A one-register conciliator for an oblivious adversary . . . . . 207 23.7 Sifters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 23.7.1 Test-and-set using sifters . . . . . . . . . . . . . . . . 211 23.7.2 Consensus using sifters . . . . . . . . . . . . . . . . . . 212 23.7.3 A better sifter for test-and-set . . . . . . . . . . . . . 214 23.8 Space bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 24 Renaming 217 24.1 Renaming . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 24.2 Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 24.3 Order-preserving renaming . . . . . . . . . . . . . . . . . . . 219 24.4 Deterministic renaming . . . . . . . . . . . . . . . . . . . . . 219 24.4.1 Wait-free renaming with 2n− 1 names . . . . . . . . . 220 24.4.2 Long-lived renaming . . . . . . . . . . . . . . . . . . . 221 24.4.3 Renaming without snapshots . . . . . . . . . . . . . . 222 24.4.3.1 Splitters . . . . . . . . . . . . . . . . . . . . . 222 24.4.3.2 Splitters in a grid . . . . . . . . . . . . . . . 223 24.4.4 Getting to 2n− 1 names in polynomial space . . . . . 225 24.4.5 Renaming with test-and-set . . . . . . . . . . . . . . . 226 24.5 Randomized renaming . . . . . . . . . . . . . . . . . . . . . . 226 24.5.1 Randomized splitters . . . . . . . . . . . . . . . . . . . 227 24.5.2 Randomized test-and-set plus sampling . . . . . . . . 227 24.5.3 Renaming with sorting networks . . . . . . . . . . . . 228 24.5.3.1 Sorting networks . . . . . . . . . . . . . . . . 228 24.5.3.2 Renaming networks . . . . . . . . . . . . . . 229 24.5.4 Randomized loose renaming . . . . . . . . . . . . . . . 231CONTENTS viii 25 Software transactional memory 232 25.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233 25.2 Basic approaches . . . . . . . . . . . . . . . . . . . . . . . . . 233 25.3 Implementing multi-word RMW . . . . . . . . . . . . . . . . 234 25.3.1 Overlapping LL/SC . . . . . . . . . . . . . . . . . . . 235 25.3.2 Representing a transaction . . . . . . . . . . . . . . . 235 25.3.3 Executing a transaction . . . . . . . . . . . . . . . . . 236 25.3.4 Proof of linearizability . . . . . . . . . . . . . . . . . . 236 25.3.5 Proof of non-blockingness . . . . . . . . . . . . . . . . 237 25.4 Improvements . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 25.5 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237 26 Obstruction-freedom 239 26.1 Why build obstruction-free algorithms? . . . . . . . . . . . . 240 26.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240 26.2.1 Lock-free implementations . . . . . . . . . . . . . . . . 240 26.2.2 Double-collect snapshots . . . . . . . . . . . . . . . . . 240 26.2.3 Software transactional memory . . . . . . . . . . . . . 241 26.2.4 Obstruction-free test-and-set . . . . . . . . . . . . . . 241 26.2.5 An obstruction-free deque . . . . . . . . . . . . . . . . 242 26.3 Boosting obstruction-freedom to wait-freedom . . . . . . . . . 245 26.3.1 Cost . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 26.4 Lower bounds for lock-free protocols . . . . . . . . . . . . . . 250 26.4.1 Contention . . . . . . . . . . . . . . . . . . . . . . . . 250 26.4.2 The class G . . . . . . . . . . . . . . . . . . . . . . . . 251 26.4.3 The lower bound proof . . . . . . . . . . . . . . . . . . 253 26.4.4 Consequences . . . . . . . . . . . . . . . . . . . . . . . 256 26.4.5 More lower bounds . . . . . . . . . . . . . . . . . . . . 257 26.5 Practical considerations . . . . . . . . . . . . . . . . . . . . . 257 27 BG simulation 258 27.1 Safe agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 258 27.2 The basic simulation algorithm . . . . . . . . . . . . . . . . . 260 27.3 Effect of failures . . . . . . . . . . . . . . . . . . . . . . . . . 261 27.4 Inputs and outputs . . . . . . . . . . . . . . . . . . . . . . . . 261 27.5 Correctness of the simulation . . . . . . . . . . . . . . . . . . 262 27.6 BG simulation and consensus . . . . . . . . . . . . . . . . . . 263CONTENTS ix 28 Topological methods 264 28.1 Basic idea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 264 28.2 k-set agreement . . . . . . . . . . . . . . . . . . . . . . . . . . 265 28.3 Representing distributed computations using topology . . . . 266 28.3.1 Simplicial complexes and process states . . . . . . . . 267 28.3.2 Subdivisions . . . . . . . . . . . . . . . . . . . . . . . 270 28.4 Impossibility of k-set agreement . . . . . . . . . . . . . . . . . 274 28.5 Simplicial maps and specifications . . . . . . . . . . . . . . . 276 28.5.1 Mapping inputs to outputs . . . . . . . . . . . . . . . 277 28.6 The asynchronous computability theorem . . . . . . . . . . . 277 28.6.1 The participating set protocol . . . . . . . . . . . . . . 278 28.7 Proving impossibility results . . . . . . . . . . . . . . . . . . . 280 28.7.1 k-connectivity . . . . . . . . . . . . . . . . . . . . . . . 280 28.7.2 Impossibility proofs for specific problems . . . . . . . 281 29 Approximate agreement 283 29.1 Algorithms for approximate agreement . . . . . . . . . . . . . 283 29.2 Lower bound on step complexity . . . . . . . . . . . . . . . . 286 III Other communication models 288 30 Self-stabilization 290 30.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291 30.2 Token ring circulation . . . . . . . . . . . . . . . . . . . . . . 291 30.2.1 Token ring circulation with mn states . . . . . . . 292 30.3 Synchronizers . . . . . . . . . . . . . . . . . . . . . . . . . . . 293 30.4 Spanning trees . . . . . . . . . . . . . . . . . . . . . . . . . . 295 30.5 Self-stabilization and local algorithms . . . . . . . . . . . . . 296 31 Population protocols and chemical reaction networks 298 31.1 Definition of a population protocol . . . . . . . . . . . . . . . 299 31.2 Stably computable predicates . . . . . . . . . . . . . . . . . . 300 31.2.1 Time complexity . . . . . . . . . . . . . . . . . . . . . 300 31.2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . 301 31.2.2.1 Leader election . . . . . . . . . . . . . . . . . 301 31.2.2.2 Distributing the output . . . . . . . . . . . . 302 31.2.2.3 Remainder mod m . . . . . . . . . . . . . . . 302 31.2.2.4 Linear threshold functions . . . . . . . . . . 302 31.2.3 Presburger arithmetic and semilinear sets . . . . . . . 303CONTENTS x 31.2.3.1 Semilinear predicates are stably computable 304 31.2.3.2 Stably computable predicates are semilinear 305 31.3 Random interactions . . . . . . . . . . . . . . . . . . . . . . . 305 32 Mobile robots 308 32.1 Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308 32.2 Two robots, no faults . . . . . . . . . . . . . . . . . . . . . . . 310 32.3 Three robots . . . . . . . . . . . . . . . . . . . . . . . . . . . 311 32.4 Many robots, with crash failures . . . . . . . . . . . . . . . . 313 33 Beeping 315 33.1 Interval coloring . . . . . . . . . . . . . . . . . . . . . . . . . 316 33.1.1 Estimating the degree . . . . . . . . . . . . . . . . . . 317 33.1.2 Picking slots . . . . . . . . . . . . . . . . . . . . . . . 317 33.1.3 Detecting collisions . . . . . . . . . . . . . . . . . . . . 317 33.2 Maximal independent set . . . . . . . . . . . . . . . . . . . . 318 33.2.1 Lower bound . . . . . . . . . . . . . . . . . . . . . . . 318 33.2.2 Upper bound with known bound on n . . . . . . . . . 320 Appendix 324 A Assignments 324 B Sample assignments from Spring 2016 325 B.1 Assignment 1: due Wednesday, 2016-02-17, at 5:00pm . . . . 325 B.1.1 Sharing the wealth . . . . . . . . . . . . . . . . . . . . 326 B.1.2 Eccentricity . . . . . . . . . . . . . . . . . . . . . . . . 328 B.1.3 Leader election on an augmented ring . . . . . . . . . 331 B.2 Assignment 2: due Wednesday, 2016-03-09, at 5:00pm . . . . 332 B.2.1 A rotor array . . . . . . . . . . . . . . . . . . . . . . . 332 B.2.2 Set registers . . . . . . . . . . . . . . . . . . . . . . . . 334 B.2.3 Bounded failure detectors . . . . . . . . . . . . . . . . 335 B.3 Assignment 3: due Wednesday, 2016-04-20, at 5:00pm . . . . 336 B.3.1 Fetch-and-max . . . . . . . . . . . . . . . . . . . . . . 336 B.3.2 Median . . . . . . . . . . . . . . . . . . . . . . . . . . 337 B.3.3 Randomized two-process test-and-set with small registers338 B.4 Presentation (for students taking CPSC 565): due Wednesday, 2016-04-27 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 B.5 CS465/CS565 Final Exam, May 10th, 2016 . . . . . . . . . . 342CONTENTS xi B.5.1 A slow register (20 points) . . . . . . . . . . . . . . . . 342 B.5.2 Two leaders (20 points) . . . . . . . . . . . . . . . . . 343 B.5.3 A splitter using one-bit registers (20 points) . . . . . . 343 B.5.4 Symmetric self-stabilizing consensus (20 points) . . . . 344 C Sample assignments from Spring 2014 346 C.1 Assignment 1: due Wednesday, 2014-01-29, at 5:00pm . . . . 346 C.1.1 Counting evil processes . . . . . . . . . . . . . . . . . 346 C.1.2 Avoiding expensive processes . . . . . . . . . . . . . . 347 C.2 Assignment 2: due Wednesday, 2014-02-12, at 5:00pm . . . . 349 C.2.1 Synchronous agreement with weak failures . . . . . . . 349 C.2.2 Byzantine agreement with contiguous faults . . . . . . 350 C.3 Assignment 3: due Wednesday, 2014-02-26, at 5:00pm . . . . 351 C.3.1 Among the elect . . . . . . . . . . . . . . . . . . . . . 351 C.3.2 Failure detectors on the cheap . . . . . . . . . . . . . . 352 C.4 Assignment 4: due Wednesday, 2014-03-26, at 5:00pm . . . . 353 C.4.1 A global synchronizer with a global clock . . . . . . . 353 C.4.2 A message-passing counter . . . . . . . . . . . . . . . 354 C.5 Assignment 5: due Wednesday, 2014-04-09, at 5:00pm . . . . 355 C.5.1 A concurrency detector . . . . . . . . . . . . . . . . . 355 C.5.2 Two-writer sticky bits . . . . . . . . . . . . . . . . . . 357 C.6 Assignment 6: due Wednesday, 2014-04-23, at 5:00pm . . . . 358 C.6.1 A rotate register . . . . . . . . . . . . . . . . . . . . . 358 C.6.2 A randomized two-process test-and-set . . . . . . . . . 360 C.7 CS465/CS565 Final Exam, May 2nd, 2014 . . . . . . . . . . . 362 C.7.1 Maxima (20 points) . . . . . . . . . . . . . . . . . . . 362 C.7.2 Historyless objects (20 points) . . . . . . . . . . . . . 363 C.7.3 Hams (20 points) . . . . . . . . . . . . . . . . . . . . . 363 C.7.4 Mutexes (20 points) . . . . . . . . . . . . . . . . . . . 365 D Sample assignments from Fall 2011 367 D.1 Assignment 1: due Wednesday, 2011-09-28, at 17:00 . . . . . 367 D.1.1 Anonymous algorithms on a torus . . . . . . . . . . . 367 D.1.2 Clustering . . . . . . . . . . . . . . . . . . . . . . . . . 368 D.1.3 Negotiation . . . . . . . . . . . . . . . . . . . . . . . . 369 D.2 Assignment 2: due Wednesday, 2011-11-02, at 17:00 . . . . . 370 D.2.1 Consensus with delivery notifications . . . . . . . . . . 370 D.2.2 A circular failure detector . . . . . . . . . . . . . . . . 371 D.2.3 An odd problem . . . . . . . . . . . . . . . . . . . . . 373 D.3 Assignment 3: due Friday, 2011-12-02, at 17:00 . . . . . . . . 374CONTENTS xii D.3.1 A restricted queue . . . . . . . . . . . . . . . . . . . . 374 D.3.2 Writable fetch-and-increment . . . . . . . . . . . . . . 375 D.3.3 A box object . . . . . . . . . . . . . . . . . . . . . . . 376 D.4 CS465/CS565 Final Exam, December 12th, 2011 . . . . . . . 377 D.4.1 Lockable registers (20 points) . . . . . . . . . . . . . . 377 D.4.2 Byzantine timestamps (20 points) . . . . . . . . . . . 378 D.4.3 Failure detectors and k-set agreement (20 points) . . . 379 D.4.4 A set data structure (20 points) . . . . . . . . . . . . . 380 E Additional sample final exams 381 E.1 CS425/CS525 Final Exam, December 15th, 2005 . . . . . . . 381 E.1.1 Consensus by attrition (20 points) . . . . . . . . . . . 381 E.1.2 Long-distance agreement (20 points) . . . . . . . . . . 382 E.1.3 Mutex appendages (20 points) . . . . . . . . . . . . . 384 E.2 CS425/CS525 Final Exam, May 8th, 2008 . . . . . . . . . . . 385 E.2.1 Message passing without failures (20 points) . . . . . . 385 E.2.2 A ring buffer (20 points) . . . . . . . . . . . . . . . . . 385 E.2.3 Leader election on a torus (20 points) . . . . . . . . . 386 E.2.4 An overlay network (20 points) . . . . . . . . . . . . . 387 E.3 CS425/CS525 Final Exam, May 10th, 2010 . . . . . . . . . . 388 E.3.1 Anti-consensus (20 points) . . . . . . . . . . . . . . . . 388 E.3.2 Odd or even (20 points) . . . . . . . . . . . . . . . . . 389 E.3.3 Atomicsnapshotarraysusingmessage-passing(20points)389 E.3.4 Priority queues (20 points) . . . . . . . . . . . . . . . 390 F I/O automata 392 F.1 Low-level view: I/O automata . . . . . . . . . . . . . . . . . . 392 F.1.1 Enabled actions . . . . . . . . . . . . . . . . . . . . . . 392 F.1.2 Executions, fairness, and traces . . . . . . . . . . . . . 393 F.1.3 Composition of automata . . . . . . . . . . . . . . . . 393 F.1.4 Hiding actions . . . . . . . . . . . . . . . . . . . . . . 394 F.1.5 Fairness . . . . . . . . . . . . . . . . . . . . . . . . . . 394 F.1.6 Specifying an automaton . . . . . . . . . . . . . . . . 395 F.2 High-level view: traces . . . . . . . . . . . . . . . . . . . . . . 395 F.2.1 Example . . . . . . . . . . . . . . . . . . . . . . . . . . 396 F.2.2 Types of trace properties . . . . . . . . . . . . . . . . 396 F.2.2.1 Safety properties . . . . . . . . . . . . . . . . 396 F.2.2.2 Liveness properties . . . . . . . . . . . . . . . 397 F.2.2.3 Other properties . . . . . . . . . . . . . . . . 398 F.2.3 Compositional arguments . . . . . . . . . . . . . . . . 398CONTENTS xiii F.2.3.1 Example . . . . . . . . . . . . . . . . . . . . 399 F.2.4 Simulation arguments . . . . . . . . . . . . . . . . . . 399 F.2.4.1 Example . . . . . . . . . . . . . . . . . . . . 400 Bibliography 401 Index 423List of Figures 2.1 Asynchronous message-passing execution . . . . . . . . . . . . 14 2.2 Asynchronous message-passing execution with FIFO channels 14 2.3 Synchronous message-passing execution . . . . . . . . . . . . 15 2.4 Asynchronous time . . . . . . . . . . . . . . . . . . . . . . . . 16 6.1 Labels in the bit-reversal ring with n = 32 . . . . . . . . . . . 47 10.1 Synthetic execution for Byzantine agreement lower bound . . 70 10.2 Synthetic execution for Byzantine agreement connectivity . . 71 12.1 Example execution of Paxos . . . . . . . . . . . . . . . . . . . 89 13.1 Failure detector classes . . . . . . . . . . . . . . . . . . . . . . 97 14.1 Figure 2 from NW98 . . . . . . . . . . . . . . . . . . . . . . 106 21.1 Snapshot from max arrays AACHE12 . . . . . . . . . . . . . 191 24.1 A 6× 6 Moir-Anderson grid . . . . . . . . . . . . . . . . . . . 224 24.2 Path through a Moir-Anderson grid . . . . . . . . . . . . . . 225 24.3 A sorting network . . . . . . . . . . . . . . . . . . . . . . . . 229 28.1 Subdivision corresponding to one round of immediate snapshot272 28.2 Subdivision corresponding to two rounds of immediate snapshot273 28.3 An attempt at 2-set agreement . . . . . . . . . . . . . . . . . 274 28.4 Output complex for renaming with n = 3, m = 4 . . . . . . . 282 C.1 Connected Byzantine nodes take over half a cut . . . . . . . . 350 xivList of Tables 18.1 Position of various types in the wait-free hierarchy . . . . . . 148 xvList of Algorithms 2.1 Client-server computation: client code . . . . . . . . . . . . . . 12 2.2 Client-server computation: server code . . . . . . . . . . . . . 12 4.1 Basic flooding algorithm . . . . . . . . . . . . . . . . . . . . . 24 4.2 Flooding with parent pointers . . . . . . . . . . . . . . . . . . 25 4.3 Convergecast . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 4.4 Flooding and convergecast combined . . . . . . . . . . . . . . . 29 5.1 AsynchBFS algorithm (from Lyn96) . . . . . . . . . . . . . . 31 6.1 LCR leader election . . . . . . . . . . . . . . . . . . . . . . . . 39 6.2 Peterson’s leader-election algorithm . . . . . . . . . . . . . . . 42 10.1 Exponential information gathering . . . . . . . . . . . . . . . . 74 10.2 Byzantine agreement: phase king . . . . . . . . . . . . . . . . . 78 13.1 Boosting completeness . . . . . . . . . . . . . . . . . . . . . . . 95 13.2 Consensus with a strong failure detector . . . . . . . . . . . . . 98 13.3 Reliable broadcast . . . . . . . . . . . . . . . . . . . . . . . . . 100 17.1 Mutual exclusion using test-and-set . . . . . . . . . . . . . . . 128 17.2 Mutual exclusion using a queue . . . . . . . . . . . . . . . . . 129 17.3 Mutual exclusion using read-modify-write . . . . . . . . . . . . 131 17.4 Peterson’s mutual exclusion algorithm for two processes . . . . 131 17.5 Implementation of a splitter . . . . . . . . . . . . . . . . . . . 135 17.6 Lamport’s Bakery algorithm . . . . . . . . . . . . . . . . . . . 138 17.7 Yang-Anderson mutex for two processes . . . . . . . . . . . . . 143 18.1 Determining the winner of a race between 2-register writes . . 153 18.2 A universal construction based on consensus . . . . . . . . . . 157 xviLIST OF ALGORITHMS xvii + 19.1 Snapshot of AAD 93 using unbounded registers . . . . . . . 161 19.2 Lattice agreement snapshot . . . . . . . . . . . . . . . . . . . . 167 19.3 Update for lattice agreement snapshot . . . . . . . . . . . . . . 168 19.4 Increasing set data structure . . . . . . . . . . . . . . . . . . . 171 19.5 Single-scanner snapshot: scan . . . . . . . . . . . . . . . . . . 174 19.6 Single-scanner snapshot: update . . . . . . . . . . . . . . . . . 174 21.1 Max register read operation . . . . . . . . . . . . . . . . . . . . 183 21.2 Max register write operations . . . . . . . . . . . . . . . . . . . 183 21.3 Recursive construction of a 2-component max array . . . . . . 188 22.1 Building 2-process TAS from 2-process consensus . . . . . . . . 193 22.2 Two-process one-shot swap from TAS . . . . . . . . . . . . . . 193 22.3 Tournament algorithm with gate . . . . . . . . . . . . . . . . . 195 22.4 Obstruction-free swap from test-and-set . . . . . . . . . . . . . 196 22.5 Wait-free swap from test-and-set AMW11 . . . . . . . . . . . 198 23.1 Consensus using adopt-commit . . . . . . . . . . . . . . . . . . 204 23.2 A 2-valued adopt-commit object . . . . . . . . . . . . . . . . . 206 23.3 Shared coin conciliator from Asp12b . . . . . . . . . . . . . . 206 23.4 Impatient first-mover conciliator from Asp12b . . . . . . . . . 208 23.5 A sifter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 23.6 Test-and-set in O(log logn) expected time . . . . . . . . . . . . 212 23.7 Sifting conciliator (from Asp12a) . . . . . . . . . . . . . . . . 213 23.8 Giakkoupis-Woelfel sifter GW12a . . . . . . . . . . . . . . . . 214 24.1 Wait-free deterministic renaming . . . . . . . . . . . . . . . . . 220 24.2 Releasing a name . . . . . . . . . . . . . . . . . . . . . . . . . 222 24.3 Implementation of a splitter . . . . . . . . . . . . . . . . . . . 223 25.1 Overlapping LL/SC . . . . . . . . . . . . . . . . . . . . . . . . 235 26.1 Obstruction-free 2-process test-and-set . . . . . . . . . . . . . 242 26.2 Obstruction-free deque . . . . . . . . . . . . . . . . . . . . . . 244 26.3 Obstruction-freedom booster from FLMS05 . . . . . . . . . . 247 27.1 Safe agreement (adapted from BGLR01) . . . . . . . . . . . . 259 28.1 Participating set . . . . . . . . . . . . . . . . . . . . . . . . . . 279 29.1 Approximate agreement . . . . . . . . . . . . . . . . . . . . . . 284LIST OF ALGORITHMS xviii 30.1 Dijkstra’s large-state token ring algorithm Dij74 . . . . . . . 292 + 33.1 Beeping a maximal independent set (from AABJ 11 . . . . . 321 B.1 Computing eccentricity in a tree . . . . . . . . . . . . . . . . . 329 B.2 Rotor array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 B.3 Two-process consensus using a rotor array . . . . . . . . . . . . 333 B.4 Max register modified to use a test-and-set bit . . . . . . . . . 336 B.5 Randomized one-shot test-and-set for two processes . . . . . . 339 B.6 Splitter using one-bit registers . . . . . . . . . . . . . . . . . . 344 C.1 Counter algorithm for Problem C.4.2. . . . . . . . . . . . . . . 355 C.2 Two-process consensus using the object from Problem C.5.1 . . 356 C.3 Implementation of a rotate register . . . . . . . . . . . . . . . 359 C.4 Randomized two-process test-and-set for C.6.2 . . . . . . . . . 360 C.5 Mutex using a swap object and register . . . . . . . . . . . . . 365 D.1 Resettable fetch-and-increment . . . . . . . . . . . . . . . . . . 376 D.2 Consensus using a lockable register . . . . . . . . . . . . . . . 377 D.3 Timestamps with n≥ 3 and one Byzantine process . . . . . . . 379 D.4 Counter from set object . . . . . . . . . . . . . . . . . . . . . . 380 F.1 Spambot as an I/O automaton . . . . . . . . . . . . . . . . . . 395Preface These are notes for the Fall 2017 semester version of the Yale course CPSC 465/565 Theory of Distributed Systems. This document also incorporates the lecture schedule and assignments, as well as some sample assignments from previous semesters. Because this is a work in progress, it will be updated frequently over the course of the semester. Notes from Spring 2016 can be found at http://www.cs.yale.edu/ homes/aspnes/classes/469/notes-2016.pdf. Notes from Spring 2014 can be found at http://www.cs.yale.edu/ homes/aspnes/classes/469/notes-2014.pdf. Notes from Fall 2011 can be found at http://www.cs.yale.edu/homes/ aspnes/classes/469/notes-2011.pdf. Notes from earlier semesters can be found at http://pine.cs.yale. edu/pinewiki/465/. Much of the structure of the course follows the textbook, Attiya and Welch’s Distributed Computing AW04, with some topics based on Lynch’s Distributed Algorithms Lyn96 and additional readings from the research literature. In most cases you’ll find these materials contain much more detail than what is presented here, so it is better to consider this document a supplement to them than to treat it as your primary source of information. Acknowledgments Many parts of these notes were improved by feedback from students taking various versions of this course, as well as others who have kindly pointed out errors in the notes after reading them online. Many of these suggestions, sadly, went unrecorded, so I must apologize to the many students who should be thanked here but whose names I didn’t keep track of in the past. However, I can thank Mike Marmar and Hao Pan in particular for suggesting improvements to some of the posted solutions, and Guy Laden for suggesting xix

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.