From Traditional Fault Tolerance to Blockchain

Description

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. Cover Half-Title Page Series Page Title Page Copyright Page Dedication Contents List of Figures List of Tables Acknowledgments Preface References 1 Introduction 1.1 Basic Concepts and Terminologies for Dependable Computing 1.1.1 System Models 1.1.2 Threat Models 1.1.3 Dependability Attributes and Evaluation Metrics 1.2 Means to Achieve Dependability 1.2.1 Fault Avoidance 1.2.2 Fault Detection and Diagnosis 1.2.3 Fault Removal 1.2.4 Fault Tolerance 1.3 System Security REFERENCES 2 Logging and Checkpointing 2.1 System Model 2.1.1 Fault Model 2.1.2 Process State and Global State 2.1.3 Piecewise Deterministic Assumption 2.1.4 Output Commit 2.1.5 Stable Storage 2.2 Checkpoint-Based Protocols 2.2.1 Uncoordinated Checkpointing 2.2.2 Tamir and Sequin Global Checkpointing Protocol 2.2.3 Chandy and Lamport Distributed Snapshot Protocol 2.2.4 Discussion 2.3 Log Based Protocols 2.3.1 Pessimistic Logging 2.3.2 Sender-Based Message Logging REFERENCES 3 Recovery-Oriented Computing 3.1 System Model 3.2 Fault Detection and Localization 3.2.1 Component Interactions Modeling and Anomaly Detection 3.2.2 Path Shapes Modeling and Root Cause Analysis 3.2.3 Inference-Based Fault Diagnosis 3.3 Microreboot 3.3.1 Microrebootable System Design Guideline 3.3.2 Automatic Recovery with Microreboot 3.3.3 Implications of the Microrebooting Technique 3.4 Overcoming Operator Errors 3.4.1 The Operator Undo Model 3.4.2 The Operator Undo Framework REFERENCES 4 Data and Service Replication 4.1 Service Replication 4.1.1 Replication Styles 4.1.2 Implementation of Service Replication 4.2 Data Replication 4.3 Optimistic Replication 4.3.1 System Models 4.3.2 Establish Ordering among Operations 4.3.3 State Transfer Systems 4.3.4 Operation Transfer System 4.3.5 Update Commitment 4.4 CAP Theorem 4.4.1 2 out 3 4.4.2 Implications of Enabling Partition Tolerance REFERENCES 5 Group Communication Systems 5.1 System Model 5.2 Sequencer Based Group Communication System 5.2.1 Normal Operation 5.2.2 Membership Change 5.2.3 Proof of Correctness 5.3 Sender Based Group Communication System 5.3.1 Total Ordering Protocol 5.3.2 Membership Change Protocol 5.3.3 Recovery Protocol 5.3.4 The Flow Control Mechanism 5.4 Vector Clock Based Group Communication System REFERENCES 6 Consensus and the Paxos Algorithms 6.1 The Consensus Problem 6.2 The Paxos Algorithm 6.2.1 Algorithm for Choosing a Value 6.2.2 Algorithm for Learning a Value 6.2.3 Proof of Correctness 6.2.4 Reasoning of the Paxos Algorithm 6.3 Multi-Paxos 6.3.1 Checkpointing and Garbage Collection 6.3.2 Leader Election and View Change 6.4 Dynamic Paxos 6.4.1 Dynamic Paxos 6.4.2 Cheap Paxos 6.5 Fast Paxos 6.5.1 The Basic Steps 6.5.2 Collision Recovery, Quorum Requirement, and Value Selection Rule 6.6 Implementations of the Paxos Family Algorithms 6.6.1 Hard Drive Failures 6.6.2 Multiple Coordinators 6.6.3 Membership Changes 6.6.4 Limited Disk Space for Logging REFERENCES 7 Byzantine Fault Tolerance 7.1 The Byzantine Generals Problem 7.1.1 System Model 7.1.2 The Oral Message Algorithms 7.1.3 Proof of Correctness for the Oral Message Algorithms 7.2 Practical Byzantine Fault Tolerance 7.2.1 System Model 7.2.2 Overview of the PBFT Algorithm 7.2.3 Normal Operation of PBFT 7.2.4 Garbage Collection 7.2.5 View Change 7.2.6 Proof of Correctness 7.2.7 Optimizations 7.3 Fast Byzantine Agreement 7.4 Speculative Byzantine Fault Tolerance 7.4.1 The Agreement Protocol 7.4.2 The View Change Protocol 7.4.3 The Checkpointing Protocol 7.4.4 Proof of Correctness REFERENCES 8 Cryptocurrency and Blockchain 8.1 History of Cryptocurrency 8.2 Bitcoin 8.2.1 Decentralized network and architecture 8.2.2 Self-contained cryptography 8.2.3 Decentralized data structure 8.2.4 Decentralized algorithms 8.3 Ethereum 8.3.1 Ethereum Computing Model 8.3.2 Block and Consensus 8.3.3 Tokenization 8.4 Attacks on Blockchain References 9 Consensus Algorithms for Blockchain 9.1 Model on Blockchain Consensus 9.1.1 Requirements on Puzzle Design 9.1.2 Zero-Knowledge Proof 9.2 Proof of Work 9.3 Proof of Resources 9.3.1 Using Storage as Resource 9.3.2 Using Computing as Resource 9.4 Virtual Mining 9.4.1 PeerCoin PoS 9.4.2 Fixed-Epoch Time Based PoS Schemes 9.4.3 Proof of Elapsed Time References 10 Blockchain Applications 10.1 The Value of Blockchain 10.1.1 Non-functional benefits 10.1.2 Functional Benefits 10.2 Blockchain-Enabled Cyber-Physical Systems 10.2.1 Cyber-Physical Systems 10.2.2 Application Categories 10.2.3 Blockchain-Enabled Operations in CPS 10.3 On Blockchain Throughput 10.3.1 On-Chain Approach 10.3.2 Off-Chain Approach 10.4 A Critical Look on Blockchain from Economy Perspective 10.4.1 Blockchain Technology from the Economic View 10.4.2 Economic Functions of Blockchain 10.4.3 Blockchain as a Financial Infrastructure References Index EULA