Fault-Tolerant Message-Passing Distributed Systems : An Algorithmic Approach

This book presents the most important fault-tolerant distributed programming abstractions and their associated distributed algorithms, in particular in terms of reliable communication and agreement, which lie at the heart of nearly all distributed applications. These programming abstractions, distributed objects or services, allow software designers and programmers to cope with asynchrony and the most important types of failures such as process crashes, message losses, and malicious behaviors of computing entities, widely known under the term "Byzantine fault-tolerance". The author introduces these notions in an incremental manner, starting from a clear specification, followed by algorithms which are first described intuitively and then proved correct. The book also presents impossibility results in classic distributed computing models, along with strategies, mainly failure detectors and randomization, that allow us to enrich these models. In this sense, the book constitutes an introduction to the science of distributed computing, with applications in all domains of distributed systems, such as cloud computing and blockchains. Each chapter comes with exercises and bibliographic notes to help the reader approach, understand, and master the fascinating field of fault-tolerant distributed computing. Preface......Page 3 Contents......Page 7 Notation......Page 18 Figures & Algorithms......Page 21 Tables......Page 26 1.1 A Few Definitions Related to Distributed Computing......Page 27 1.2.1 The Problem......Page 31 1.2.3 Trying to Solve the Problem: Attempt 2......Page 33 1.2.4 An Impossibility Result......Page 34 1.3.1 The Problem......Page 35 1.3.2 The Notion of a Message Adversary......Page 36 1.3.3 The TREE-AD Message Adversary......Page 37 1.3.4 From Message Adversary to Process Mobility......Page 39 1.4 Main Distributed Computing Models Used in This Book......Page 40 1.5 Distributed Computing Versus Parallel Computing......Page 41 1.7 Bibliographic Notes......Page 42 1.8 Exercises and Problems......Page 43 --- Reliable Broadcast Communication Abstraction......Page 45 2.1.1 From Best Effort to Guaranteed Reliability......Page 46 2.1.2 Uniform Reliable Broadcast (URB-broadcast)......Page 47 2.1.3 Building the URB-broadcast Abstraction in CAMPn,t[∅]......Page 48 2.2.1 “First In, First Out” (FIFO) Message Delivery......Page 50 2.2.2 “Causal Order” (CO) Message Delivery......Page 52 2.2.3 From FIFO-broadcast to CO-broadcast......Page 54 2.2.4 From URB-broadcast to CO-broadcast: Capturing Causal Past in a Vector......Page 57 2.2.5 The Total Order Broadcast Abstraction Requires More......Page 61 2.5 Exercises and Problems......Page 62 3.1.1 Fairness Notions for Channels......Page 64 3.1.2 Fair Channel (FC) and Fair Lossy Channel......Page 65 3.1.3 Reliable Channel in the Presence of Process Crashes......Page 66 3.2 URB-broadcast in CAMPn,t[- FC]......Page 67 3.2.1 URB-broadcast in CAMPn,t[- FC, t < n/2]......Page 68 3.2.2 An Impossibility Result......Page 69 3.3.1 The Concept of a Failure Detector......Page 70 3.3.2 Formal Definitions......Page 71 3.4.1 Definition of the Failure Detector Class Θ......Page 72 3.4.3 Building a Failure Detector Θ in CAMPn,t[- FC, t < n/2]......Page 73 3.5.1 The Quiescence Property......Page 74 3.5.2 Quiescent URB-broadcast Based on a Perfect Failure Detector......Page 75 3.5.3 The Class HB of Heartbeat Failure Detectors......Page 77 3.5.4 Quiescent URB-broadcast in CAMPn,t[- FC, Θ,HB]......Page 79 3.7 Bibliographic Notes......Page 81 3.8 Exercises and Problems......Page 82 4.1 Byzantine Processes and Properties of the Model BAMPn,t[t < n/3]......Page 84 4.2.1 Definition......Page 85 4.2.3 A No-Duplicity Broadcast Algorithm......Page 86 4.3 The Byzantine Reliable Broadcast Abstraction......Page 88 4.4.1 A Byzantine Reliable Broadcast Algorithm for BAMPn,t[t < n/3]......Page 89 4.4.2 Correctness Proof......Page 90 4.4.3 Benefiting from Message Asynchrony......Page 91 4.5 Time and Message-Efficient Byzantine Reliable Broadcast......Page 92 4.5.2 Correctness Proof......Page 93 4.6 Summary......Page 95 4.8 Exercises and Problems......Page 96 --- R/W Register Communication Abstraction......Page 97 5.1.1 Concurrent Objects and Registers......Page 98 5.1.2 The Notion of a Regular Register......Page 99 5.1.3 Registers Defined from a Sequential Specification......Page 100 5.2.1 Processes, Operations, and Events......Page 102 5.2.2 Histories......Page 103 5.2.4 A Formal Definition of Sequential Consistency......Page 105 5.3.2 Atomicity Is Composable......Page 106 5.3.3 Sequential Consistency Is Not Composable......Page 108 5.4.1 Upper Bound on t for Atomicity......Page 109 5.4.2 Upper Bound on t for Sequential Consistency......Page 110 5.4.3 Lower Bounds on the Durations of Read andWrite Operations......Page 111 5.6 Bibliographic Notes......Page 114 5.7 Exercises and Problems......Page 115 6.1 A Structural View......Page 116 6.2.1 Problem Specification......Page 117 6.2.2 Implementing an SWMR Regular Register in CAMPn,t[t < n/2]......Page 118 6.2.3 Proof of the SWMR Regular Register Construction......Page 120 6.3.2 From Regularity to Atomicity......Page 121 6.4.1 Replacing Sequence Numbers by Timestamps......Page 122 6.4.3 Proof of the MWMR Atomic Register Construction......Page 123 6.5.2 Algorithms Based on a Total Order Broadcast Abstraction......Page 126 6.5.3 A TO-broadcast-based Algorithm with Local (Fast) Read Operations......Page 127 6.5.4 A TO-broadcast-based Algorithm with Local (Fast) Write Operations......Page 128 6.5.5 An Algorithm Based on Logical Time......Page 129 6.5.6 Proof of the Logical Time-based Algorithm......Page 133 6.7 Bibliographic Notes......Page 136 6.8 Exercises and Problems......Page 137 7.1.1 Definition of the Class of Quorum Failure Detectors......Page 139 7.1.2 Implementing a Failure Detector Σ When t < n/2......Page 140 7.1.3 A Σ-based Construction of an SWSR Atomic Register......Page 141 7.2.2 The Extraction Algorithm......Page 142 7.2.3 Correctness of the Extraction Algorithm......Page 144 7.3 Comparing the Failure Detectors Classes Θ and Σ......Page 145 7.4.1 From Atomic Registers to URB-broadcast......Page 146 7.4.2 Atomic Registers Are Strictly Stronger than URB-broadcast......Page 147 7.7 Exercise and Problem......Page 148 8 Broadcast Abstraction suited to Family of R/W Implementable Objects......Page 150 8.1.1 Definition......Page 151 8.1.2 Implementing SCD-broadcast in CAMPn,t[t < n/2]......Page 152 8.1.3 Cost and Proof of the Algorithm......Page 154 8.2.1 Building an MWMR Atomic Register in CAMPn,t[SCD-broadcast]......Page 158 8.2.2 Cost and Proof of Correctness......Page 160 8.2.3 From Atomicity to Sequential Consistency......Page 161 8.2.4 From MWMR Registers to an Atomic Snapshot Object......Page 162 8.3.1 Counter Object......Page 163 8.3.2 Implementation of an Atomic Counter Object......Page 164 8.3.3 Implementation of a Sequentially Consistent Counter Object......Page 165 8.4.1 The Lattice Agreement Task......Page 166 8.5.1 From Snapshot to SCD-broadcast......Page 167 8.5.2 Proof of the Algorithm......Page 169 8.6 Summary......Page 170 8.7 Bibliographic Notes......Page 171 8.8 Exercises and Problems......Page 172 9.1.2 Reminder on Possible Behaviors of a Byzantine Process......Page 173 9.1.3 SWMR Atomic Registers Despite Byzantine Processes: Definition......Page 174 9.2 An Impossibility Result......Page 175 9.3.2 An Algorithm for Multi-shot Byzantine Reliable Broadcast......Page 177 9.4.1 Description of the Algorithm......Page 179 9.4.2 Comparison with the Crash Failure Model......Page 181 9.5.2 Proof of the Termination Properties......Page 182 9.5.3 Proof of the Consistency (Atomicity) Properties......Page 183 9.6.1 One-shot Write-snapshot Object......Page 184 9.6.2 Correct-only Agreement Object......Page 185 9.7 Summary......Page 186 9.9 Exercises and Problems......Page 187 --- Agreement in Sync Systems......Page 189 10.1.1 Definition......Page 190 10.1.2 A Simple (Unfair) Consensus Algorithm......Page 191 10.1.3 A Simple (Fair) Consensus Algorithm......Page 192 10.2.1 Definition......Page 194 10.2.3 An Interactive Consistency Algorithm......Page 195 10.2.4 Proof of the Algorithm......Page 196 10.3 Lower Bound on the Number of Rounds......Page 198 10.3.2 The (t + 1) Lower Bound......Page 199 10.3.3 Proof of the Lemmas......Page 200 10.6 Exercises and Problems......Page 203 11.1.1 Early Deciding vs Early Stopping......Page 205 11.1.2 An Early Decision Predicate......Page 206 11.1.3 An Early Deciding and Stopping Algorithm......Page 207 11.1.4 Correctness Proof......Page 208 11.1.5 On Early Decision Predicates......Page 210 11.1.6 Early Deciding and Stopping Consensus......Page 211 11.2.1 A Knowledge-Based Unbeatable Predicate......Page 212 11.2.3 An Algorithm Based on the Predicate PREF0(): CGM......Page 213 11.3.1 The Condition-based Approach in Synchronous Systems......Page 216 11.3.2 Legality and Maximality of a Condition......Page 217 11.3.3 Hierarchy of Legal Conditions......Page 219 11.3.5 A Synchronous Condition-based Consensus Algorithm......Page 220 11.3.6 Proof of the Algorithm......Page 221 11.4.1 Fast Perfect Failure Detectors......Page 223 11.4.3 A Simple Consensus Algorithm Based on a Fast Failure Detector......Page 224 11.4.4 An Early Deciding and Stopping Algorithm......Page 225 11.6 Bibliographic Notes......Page 228 11.7 Exercises and Problems......Page 229 12.1.1 Definition of Simultaneous Consensus......Page 230 12.1.3 Failure Pattern, Failure Discovery, and Waste......Page 231 12.1.4 A Clean Round and the Horizon of a Round......Page 232 12.2.1 An Optimal Algorithm......Page 233 12.2.2 Proof of the Algorithm......Page 235 12.3.2 A Simple Algorithm......Page 237 12.4.2 Proof of the Algorithm......Page 239 12.6 Bibliographic Notes......Page 242 12.7 Exercises and Problems......Page 243 13.1.1 Definition of Non-blocking Atomic Commitment......Page 245 13.1.2 A Simple Non-blocking Atomic Commitment Algorithm......Page 246 13.2.2 An Impossibility Result......Page 247 13.4.1 A Fast Commit and Weak Fast Abort Algorithm......Page 250 13.4.2 Proof of the Algorithm......Page 252 13.5.1 Fast Abort andWeak Fast Commit......Page 255 13.6 Summary......Page 256 13.7 Bibliographic Notes......Page 257 13.8 Exercises and Problems......Page 258 14 Consensus in Sync Systems prone to Byzantine Process Failures......Page 259 14.1.2 A Consensus Definition for the Byzantine Failure Model......Page 260 14.2.1 An Algorithm for n = 4 and t = 1......Page 261 14.2.2 Proof of the Algorithm......Page 262 14.3 An Upper Bound on the Number of Byzantine Processes......Page 263 14.4 A Byzantine Consensus Algorithm for BSMPn,t[t < n/3]......Page 265 14.4.1 Base Data Structure: a Tree......Page 266 14.4.2 EIG Algorithm......Page 267 14.4.3 Example of an Execution......Page 268 14.4.4 Proof of the EIG Algorithm......Page 269 14.5.2 Presentation of the Algorithm......Page 271 14.5.3 Proof and Properties of the Algorithm......Page 272 14.6.1 Motivation......Page 273 14.6.2 A Reduction Algorithm......Page 274 14.6.3 Proof of the Multivalued to Binary Reduction......Page 275 14.7.1 Synchronous Model with Signed Messages......Page 277 14.7.3 A Synchronous Signature-Based Consensus Algorithm......Page 278 14.7.4 Proof of the Algorithm......Page 279 14.9 Bibliographic Notes......Page 280 14.10 Exercises and Problems......Page 281 --- Agreement in Async Systems......Page 282 15.1.1 Definition......Page 283 15.1.2 A Fundamental Result......Page 284 15.1.3 The Stacking Approach......Page 285 15.1.4 A Snapshot-based Implementation of Renaming......Page 286 15.1.5 Proof of the Algorithm......Page 287 15.2.1 Definition......Page 288 15.2.3 Proof of the Algorithm......Page 289 15.3.1 Definition......Page 291 15.3.2 A Direct Implementation of Safe Agreement in CAMPn,t[t < n/2]......Page 292 15.3.3 Proof of the Algorithm......Page 293 15.4 Summary......Page 295 15.6 Exercises and Problems......Page 296 16.1.1 Total Order Broadcast: Definition......Page 298 16.1.2 A Map of Communication Abstractions......Page 299 16.2.2 Description of the Algorithm......Page 300 16.2.3 Proof of the Algorithm......Page 302 16.3 Consensus and TO-broadcast Are Equivalent......Page 303 16.4.1 State Machine Replication......Page 304 16.4.2 Sequentially-Defined Abstractions (Objects)......Page 305 16.5 A Simple Consensus-based Universal Construction......Page 306 16.6 Agreement vs Mutual Exclusion......Page 307 16.7.1 Definition......Page 308 16.7.2 Implementation of a Ledger in CAMPn,t[TO-broadcast]......Page 310 16.8.1 The Intuition That Underlies the Impossibility......Page 311 16.8.2 Refining the Definition of CAMPn,t[∅]......Page 312 16.8.3 Notion of Valence of a Global State......Page 314 16.8.4 Consensus Is Impossible in CAMPn,1[∅]......Page 315 16.9.1 The Main Question......Page 320 16.9.3 An Illustration of Herlihy’s Hierarchy......Page 321 16.10 Summary......Page 324 16.11 Bibliographic Notes......Page 325 16.12 Exercises and Problems......Page 326 17.1 Enriching an Asynchronous System to Implement Consensus......Page 328 17.2.2 A Binary Consensus Algorithm......Page 329 17.2.3 Proof of the Algorithm......Page 330 17.3.1 Enriching CAMPn,t[∅] with a Perfect Failure Detector......Page 332 17.4.1 TheWeakest Failure Detector to Implement Consensus......Page 334 17.4.2 Implementing Consensus in CAMPn,t[t < n/2, Ω]......Page 335 17.4.3 Proof of the Algorithm......Page 338 17.4.6 Saving Broadcast Instances......Page 340 17.5.1 Asynchronous Randomized Models......Page 341 17.5.3 Randomized Binary Consensus in CAMPn,t[t < n/2, LC]......Page 342 17.5.4 Randomized Binary Consensus in CAMPn,t[t < n/2, CC]......Page 345 17.6.1 The Hybrid Approach: Failure Detector and Randomization......Page 348 17.6.2 A Hybrid Binary Consensus Algorithm......Page 349 17.7 A Paxos-inspired Consensus Algorithm......Page 350 17.7.2 Consensus Algorithm......Page 351 17.7.3 An Implementation of Alpha in CAMPn,t[t < n/2]......Page 352 17.8.1 A Reduction Algorithm......Page 355 17.8.2 Proof of the Reduction Algorithm......Page 356 17.9.2 A One Communication Step Algorithm......Page 357 17.9.3 Proof of the Early Deciding Algorithm......Page 358 17.10 Summary......Page 359 17.11 Bibliographic Notes......Page 360 17.12 Exercises and Problems......Page 361 18.1 The Two Facets of Failure Detectors......Page 363 18.1.2 The Computability Point of View: Abstraction Ranking......Page 364 18.2 Ω in CAMPn,t[∅]: a Direct Impossibility Proof......Page 365 18.3.1 Reminder: Definition of the Class P of Perfect Failure Detectors......Page 366 18.3.2 Use of an Underlying Synchronous System......Page 367 18.3.3 Applications Generating a Fair Communication Pattern......Page 368 18.3.4 The Theta Assumption......Page 369 18.4.3 Eventually Synchronous Systems......Page 371 18.5.1 Motivation and System Model......Page 373 18.5.2 A Monitoring Algorithm......Page 374 18.6.2 A Monitoring-Based Adaptive Algorithm for the Failure Detector Class P......Page 376 18.6.3 Proof the Algorithm......Page 378 18.7.1 The t-Source Assumption and the Model CAMPn,t[t-SOURCE]......Page 379 18.7.2 Electing an Eventual Leader in CAMPn,t[t-SOURCE]......Page 380 18.7.3 Proof of the Algorithm......Page 381 18.8.1 A Query/Response Pattern......Page 382 18.8.2 Electing an Eventual Leader in CAMPn,t[t-MS PAT]......Page 384 18.8.3 Proof of the Algorithm......Page 385 18.9 Building Ω in a Hybrid Model......Page 386 18.10.2 The CORE Communication Abstraction......Page 387 18.10.3 Construction of a Common Coin with a Constant Bias......Page 390 18.11 Summary......Page 391 18.12 Bibliographic notes......Page 392 18.13 Exercises and Problems......Page 393 19.1.1 Definition of Byzantine Consensus (Reminder)......Page 394 19.1.3 On the Weakest Synchrony Assumption for Byzantine Consensus......Page 395 19.2.2 A Binary Byzantine Consensus Algorithm......Page 396 19.2.3 Proof of the Algorithm......Page 397 19.3.1 The Binary-Value Broadcast Abstraction......Page 398 19.3.2 A Binary Randomized Consensus Algorithm......Page 400 19.3.3 Proof of the BV-Based Binary Byzantine Consensus Algorithm......Page 402 19.3.4 From Decision to Decision and Termination......Page 404 19.4.1 A Reduction Algorithm......Page 405 19.4.2 Proof of the Reduction Algorithm......Page 407 19.5.2 An Algorithm Implementing VBB-broadcast......Page 408 19.5.3 Proof of the VBB-broadcast Algorithm......Page 410 19.5.4 A VBB-Based Multivalued to Binary Byzantine Consensus Reduction......Page 411 19.5.5 Proof of the VBB-Based Reduction Algorithm......Page 412 19.6 Summary......Page 413 19.7 Appendix: Proof-of-Work (PoW) Seen as Eventual Byzantine Agreement......Page 414 19.8 Bibliographic Notes......Page 415 19.9 Exercises and Problems......Page 416 20.1.1 Definitions......Page 419 20.1.2 Examples of Use of a Quorum System......Page 420 20.1.3 A Few Classical Quorums......Page 421 20.1.4 Quorum Composition......Page 422 20.2.1 Cipher, Keys, and Signatures......Page 423 20.2.2 How to Build a Secret Key: Diffie-Hellman’s Algorithm......Page 424 20.2.4 How to Share a Secret: Shamir’s Algorithm......Page 425 20.3.1 On Regular Graphs......Page 426 20.3.2 Hypercube......Page 427 20.3.3 de Bruijn Graphs......Page 428 20.3.4 Kautz Graphs......Page 429 20.3.5 Undirected de Bruijn and Kautz Graphs......Page 430 20.4 Bibliographic Notes......Page 431 Afterword......Page 432 Biblio......Page 437 Index......Page 459