This book covers the most essential techniques for designing and building dependable distributed systems, from traditional fault tolerance to the blockchain technology. Topics include checkpointing and logging, recovery-orientated computing, replication, distributed consensus, Byzantine fault tolerance, as well as blockchain.
This book intentionally includes traditional fault tolerance techniques so that readers can appreciate better the huge benefits brought by the blockchain technology and why it has been touted as a disruptive technology, some even regard it at the same level of the Internet. This book also expresses a grave concern on using traditional consensus algorithms in blockchain because with the limited scalability of such algorithms, the primary benefits of using blockchain in the first place, such as decentralization and immutability, could be easily lost under cyberattacks.
Table of Contents
List of Figures xiii
List of Tables xix
Acknowledgments xxi
Preface xxiii
References xxix
1 Introduction 1
1.1 Basic Concepts and Terminologies for Dependable Computing 2
1.1.1 System Models 2
1.1.2 Threat Models 3
1.1.3 Dependability Attributes and Evaluation Metrics 6
1.2 Means to Achieve Dependability 9
1.2.1 Fault Avoidance 9
1.2.2 Fault Detection and Diagnosis 9
1.2.3 Fault Removal 10
1.2.4 Fault Tolerance 11
1.3 System Security 13
References 18
2 Logging and Checkpointing 21
2.1 System Model 22
2.1.1 Fault Model 23
2.1.2 Process State and Global State 23
2.1.3 Piecewise Deterministic Assumption 26
2.1.4 Output Commit 26
2.1.5 Stable Storage 27
2.2 Checkpoint-Based Protocols 27
2.2.1 Uncoordinated Checkpointing 27
2.2.2 Tamir and Sequin Global Checkpointing Protocol 29
2.2.3 Chandy and Lamport Distributed Snapshot Protocol 35
2.2.4 Discussion 38
2.3 Log Based Protocols 40
2.3.1 Pessimistic Logging 42
2.3.2 Sender-Based Message Logging 51
References 60
3 Recovery-Oriented Computing 63
3.1 System Model 65
3.2 Fault Detection and Localization 68
3.2.1 Component Interactions Modeling and Anomaly Detection 72
3.2.2 Path Shapes Modeling and Root Cause Analysis 76
3.2.3 Inference-Based Fault Diagnosis 80
3.3 Microreboot 89
3.3.1 Microrebootable System Design Guideline 90
3.3.2 Automatic Recovery with Microreboot 91
3.3.3 Implications of the Microrebooting Technique 92
3.4 Overcoming Operator Errors 93
3.4.1 The Operator Undo Model 94
3.4.2 The Operator Undo Framework 95
References 99
4 Data and Service Replication 103
4.1 Service Replication 105
4.1.1 Replication Styles 107
4.1.2 Implementation of Service Replication 109
4.2 Data Replication 111
4.3 Optimistic Replication 116
4.3.1 System Models 117
4.3.2 Establish Ordering among Operations 119
4.3.3 State Transfer Systems 122
4.3.4 Operation Transfer System 126
4.3.5 Update Commitment 131
4.4 CAP Theorem 136
4.4.1 2 out 3 139
4.4.2 Implications of Enabling Partition Tolerance 140
References 143
5 Group Communication Systems 147
5.1 System Model 149
5.2 Sequencer Based Group Communication System 152
5.2.1 Normal Operation 153
5.2.2 Membership Change 157
5.2.3 Proof of Correctness 165
5.3 Sender Based Group Communication System 166
5.3.1 Total Ordering Protocol 167
5.3.2 Membership Change Protocol 174
5.3.3 Recovery Protocol 183
5.3.4 The Flow Control Mechanism 190
5.4 Vector Clock Based Group Communication System 192
References 197
6 Consensus and the Paxos Algorithms 199
6.1 The Consensus Problem 200
6.2 The Paxos Algorithm 202
6.2.1 Algorithm for Choosing a Value 202
6.2.2 Algorithm for Learning a Value 204
6.2.3 Proof of Correctness 204
6.2.4 Reasoning of the Paxos Algorithm 206
6.3 Multi-Paxos 212
6.3.1 Checkpointing and Garbage Collection 213
6.3.2 Leader Election and View Change 214
6.4 Dynamic Paxos 216
6.4.1 Dynamic Paxos 217
6.4.2 Cheap Paxos 220
6.5 Fast Paxos 227
6.5.1 The Basic Steps 228
6.5.2 Collision Recovery, Quorum Requirement, and Value Selection Rule 229
6.6 Implementations of the Paxos Family Algorithms 235
6.6.1 Hard Drive Failures 236
6.6.2 Multiple Coordinators 236
6.6.3 Membership Changes 237
6.6.4 Limited Disk Space for Logging 241
References 242
7 Byzantine Fault Tolerance 245
7.1 The Byzantine Generals Problem 246
7.1.1 System Model 247
7.1.2 The Oral Message Algorithms 250
7.1.3 Proof of Correctness for the Oral Message Algorithms 260
7.2 Practical Byzantine Fault Tolerance 261
7.2.1 System Model 262
7.2.2 Overview of the PBFT Algorithm 263
7.2.3 Normal Operation of PBFT 265
7.2.4 Garbage Collection 267
7.2.5 View Change 268
7.2.6 Proof of Correctness 271
7.2.7 Optimizations 273
7.3 Fast Byzantine Agreement 277
7.4 Speculative Byzantine Fault Tolerance 278
7.4.1 The Agreement Protocol 279
7.4.2 The View Change Protocol 283
7.4.3 The Checkpointing Protocol 288
7.4.4 Proof of Correctness 288
References 290
8 Cryptocurrency and Blockchain 295
8.1 History of Cryptocurrency 295
8.2 Bitcoin 298
8.2.1 Decentralized Network and Architecture 301
8.2.2 Self-Contained Cryptography 302
8.2.3 Decentralized Data Structure 304
8.2.4 Decentralized Algorithms 313
8.3 Ethereum 317
8.3.1 Ethereum Computing Model 318
8.3.2 Block and Consensus 326
8.3.3 Tokenization 340
8.4 Attacks on Blockchain 342
References 347
9 Consensus Algorithms for Blockchain 349
9.1 Model on Blockchain Consensus 353
9.1.1 Requirements on Puzzle Design 354
9.1.2 Zero-Knowledge Proof 355
9.2 Proof of Work 356
9.3 Proof of Resources 357
9.3.1 Using Storage as Resource 357
9.3.2 Using Computing as Resource 359
9.4 Virtual Mining 360
9.4.1 PeerCoin PoS 360
9.4.2 Fixed-Epoch Time Based PoS Schemes 368
9.4.3 Proof of Elapsed Time 371
References 375
10 Blockchain Applications 377
10.1 The Value of Blockchain 378
10.1.1 Non-Functional Benefits 379
10.1.2 Functional Benefits 382
10.2 Blockchain-Enabled Cyber-Physical Systems 383
10.2.1 Cyber-Physical Systems 383
10.2.2 Application Categories 385
10.2.3 Blockchain-Enabled Operations in CPS 390
10.3 On Blockchain Throughput 398
10.3.1 On-Chain Approach 399
10.3.2 Off-Chain Approach 402
10.4 A Critical Look on Blockchain from Economy Perspective 408
10.4.1 Blockchain Technology from the Economic View 409
10.4.2 Economic Functions of Blockchain 412
10.4.3 Blockchain as a Financial Infrastructure 416
References 419
Index 427
