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

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