From Traditional Fault Tolerance to Blockchain

Dr. Zhao received the PhD degree in Electrical and Computer Engineering from the University of California, Santa Barbara, in 2002. He is now a Full Professor in the Department of Electrical Engineering and Computer Science at Cleveland State University. He has more than 200 academic publications and three of his recent research papers in the dependable distributed computing area have won the best paper awards. Dr. Zhao also has two US utility patents and a patent application on blockchain under review.

• List of Figures xiiiList of Tables xixAcknowledgments xxiPreface xxiiiReferences xxix1 Introduction 11.1 Basic Concepts and Terminologies for Dependable Computing 21.1.1 System Models 21.1.2 Threat Models 31.1.3 Dependability Attributes and Evaluation Metrics 61.2 Means to Achieve Dependability 91.2.1 Fault Avoidance 91.2.2 Fault Detection and Diagnosis 91.2.3 Fault Removal 101.2.4 Fault Tolerance 111.3 System Security 13References 182 Logging and Checkpointing 212.1 System Model 222.1.1 Fault Model 232.1.2 Process State and Global State 232.1.3 Piecewise Deterministic Assumption 262.1.4 Output Commit 262.1.5 Stable Storage 272.2 Checkpoint-Based Protocols 272.2.1 Uncoordinated Checkpointing 272.2.2 Tamir and Sequin Global Checkpointing Protocol 292.2.3 Chandy and Lamport Distributed Snapshot Protocol 352.2.4 Discussion 382.3 Log Based Protocols 402.3.1 Pessimistic Logging 422.3.2 Sender-Based Message Logging 51References 603 Recovery-Oriented Computing 633.1 System Model 653.2 Fault Detection and Localization 683.2.1 Component Interactions Modeling and Anomaly Detection 723.2.2 Path Shapes Modeling and Root Cause Analysis 763.2.3 Inference-Based Fault Diagnosis 803.3 Microreboot 893.3.1 Microrebootable System Design Guideline 903.3.2 Automatic Recovery with Microreboot 913.3.3 Implications of the Microrebooting Technique 923.4 Overcoming Operator Errors 933.4.1 The Operator Undo Model 943.4.2 The Operator Undo Framework 95References 994 Data and Service Replication 1034.1 Service Replication 1054.1.1 Replication Styles 1074.1.2 Implementation of Service Replication 1094.2 Data Replication 1114.3 Optimistic Replication 1164.3.1 System Models 1174.3.2 Establish Ordering among Operations 1194.3.3 State Transfer Systems 1224.3.4 Operation Transfer System 1264.3.5 Update Commitment 1314.4 CAP Theorem 1364.4.1 2 out 3 1394.4.2 Implications of Enabling Partition Tolerance 140References 1435 Group Communication Systems 1475.1 System Model 1495.2 Sequencer Based Group Communication System 1525.2.1 Normal Operation 1535.2.2 Membership Change 1575.2.3 Proof of Correctness 1655.3 Sender Based Group Communication System 1665.3.1 Total Ordering Protocol 1675.3.2 Membership Change Protocol 1745.3.3 Recovery Protocol 1835.3.4 The Flow Control Mechanism 1905.4 Vector Clock Based Group Communication System 192References 1976 Consensus and the Paxos Algorithms 1996.1 The Consensus Problem 2006.2 The Paxos Algorithm 2026.2.1 Algorithm for Choosing a Value 2026.2.2 Algorithm for Learning a Value 2046.2.3 Proof of Correctness 2046.2.4 Reasoning of the Paxos Algorithm 2066.3 Multi-Paxos 2126.3.1 Checkpointing and Garbage Collection 2136.3.2 Leader Election and View Change 2146.4 Dynamic Paxos 2166.4.1 Dynamic Paxos 2176.4.2 Cheap Paxos 2206.5 Fast Paxos 2276.5.1 The Basic Steps 2286.5.2 Collision Recovery, Quorum Requirement, and Value Selection Rule 2296.6 Implementations of the Paxos Family Algorithms 2356.6.1 Hard Drive Failures 2366.6.2 Multiple Coordinators 2366.6.3 Membership Changes 2376.6.4 Limited Disk Space for Logging 241References 2427 Byzantine Fault Tolerance 2457.1 The Byzantine Generals Problem 2467.1.1 System Model 2477.1.2 The Oral Message Algorithms 2507.1.3 Proof of Correctness for the Oral Message Algorithms 2607.2 Practical Byzantine Fault Tolerance 2617.2.1 System Model 2627.2.2 Overview of the PBFT Algorithm 2637.2.3 Normal Operation of PBFT 2657.2.4 Garbage Collection 2677.2.5 View Change 2687.2.6 Proof of Correctness 2717.2.7 Optimizations 2737.3 Fast Byzantine Agreement 2777.4 Speculative Byzantine Fault Tolerance 2787.4.1 The Agreement Protocol 2797.4.2 The View Change Protocol 2837.4.3 The Checkpointing Protocol 2887.4.4 Proof of Correctness 288References 2908 Cryptocurrency and Blockchain 2958.1 History of Cryptocurrency 2958.2 Bitcoin 2988.2.1 Decentralized Network and Architecture 3018.2.2 Self-Contained Cryptography 3028.2.3 Decentralized Data Structure 3048.2.4 Decentralized Algorithms 3138.3 Ethereum 3178.3.1 Ethereum Computing Model 3188.3.2 Block and Consensus 3268.3.3 Tokenization 3408.4 Attacks on Blockchain 342References 3479 Consensus Algorithms for Blockchain 3499.1 Model on Blockchain Consensus 3539.1.1 Requirements on Puzzle Design 3549.1.2 Zero-Knowledge Proof 3559.2 Proof of Work 3569.3 Proof of Resources 3579.3.1 Using Storage as Resource 3579.3.2 Using Computing as Resource 3599.4 Virtual Mining 3609.4.1 PeerCoin PoS 3609.4.2 Fixed-Epoch Time Based PoS Schemes 3689.4.3 Proof of Elapsed Time 371References 37510 Blockchain Applications 37710.1 The Value of Blockchain 37810.1.1 Non-Functional Benefits 37910.1.2 Functional Benefits 38210.2 Blockchain-Enabled Cyber-Physical Systems 38310.2.1 Cyber-Physical Systems 38310.2.2 Application Categories 38510.2.3 Blockchain-Enabled Operations in CPS 39010.3 On Blockchain Throughput 39810.3.1 On-Chain Approach 39910.3.2 Off-Chain Approach 40210.4 A Critical Look on Blockchain from Economy Perspective 40810.4.1 Blockchain Technology from the Economic View 40910.4.2 Economic Functions of Blockchain 41210.4.3 Blockchain as a Financial Infrastructure 416References 419Index 427