Оглавление
Wenbing Zhao. From Traditional Fault Tolerance to Blockchain
Table of Contents
List of Illustrations
List of Tables
Guide
Pages
From Traditional Fault Tolerance to Blockchain
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.1.3.1 Availability
1.1.3.2 Reliability
1.1.3.3 Integrity
1.1.3.4 Maintainability
1.1.3.5 Safety
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
EXAMPLE 2.1
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
EXAMPLE 2.2
2.2.2 Tamir and Sequin Global Checkpointing Protocol
2.2.2.1 Protocol Description
EXAMPLE 2.3
2.2.2.2 Correctness of the Protocol
2.2.3 Chandy and Lamport Distributed Snapshot Protocol
2.2.3.1 Protocol Description
EXAMPLE 2.4
2.2.4 Discussion
2.3 Log Based Protocols
2.3.1 Pessimistic Logging
EXAMPLE 2.5
2.3.1.1 Benefits of Pessimistic Logging
2.3.1.2 Discussion
2.3.1.3 Pessimistic Logging Cost
2.3.2 Sender-Based Message Logging
2.3.2.1 Data Structures
2.3.2.2 Normal Operation of the Message Logging Protocol
EXAMPLE 2.6
2.3.2.3 Recovery Mechanism
2.3.2.4 Limitations and Correctness
EXAMPLE 2.7
2.3.2.5 Discussion
REFERENCES
3. Recovery-Oriented Computing
3.1 System Model
3.2 Fault Detection and Localization
EXAMPLE 3.1
EXAMPLE 3.2
3.2.1 Component Interactions Modeling and Anomaly Detection
EXAMPLE 3.3
EXAMPLE 3.4
3.2.2 Path Shapes Modeling and Root Cause Analysis
EXAMPLE 3.5
EXAMPLE 3.6
3.2.3 Inference-Based Fault Diagnosis
3.2.3.1 Component States Logging
3.2.3.2 Dependency Graph Construction
EXAMPLE 3.7
3.2.3.3Fault Diagnosis
EXAMPLE 3.8
EXAMPLE 3.9
EXAMPLE 3.10
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
EXAMPLE 3.11
EXAMPLE 3.12
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
EXAMPLE 4.1
EXAMPLE 4.2
4.3 Optimistic Replication
4.3.1 System Models
4.3.2 Establish Ordering among Operations
4.3.3 State Transfer Systems
4.3.3.1 Version Vectors
EXAMPLE 4.3
4.3.4 Operation Transfer System
4.3.4.1 Propagation Using Vector Clocks
EXAMPLE 4.4
4.3.4.2 Propagation Using Timestamp Matrices
EXAMPLE 4.5
4.3.5 Update Commitment
4.3.5.1 Ack Vector
EXAMPLE 4.6
4.3.5.2 Timestamp Matrix
EXAMPLE 4.7
4.4 CAP Theorem
EXAMPLE 4.8
4.4.1 2 out 3
4.4.1.1 CA System
4.4.1.2 CP System
4.4.1.3 PA System
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
EXAMPLE 5.1
5.2.2 Membership Change
EXAMPLE 5.2
EXAMPLE 5.3
EXAMPLE 5.4
5.2.3 Proof of Correctness
5.3 Sender Based Group Communication System
5.3.1 Total Ordering Protocol
5.3.1.1 Rules on receiving a regular token
5.3.1.2 Rules on receiving a regular message
5.3.1.3 Rules on regular token retransmission
5.3.1.4 Examples
EXAMPLE 5.5
EXAMPLE 5.6
EXAMPLE 5.7
5.3.2 Membership Change Protocol
5.3.2.1 Events and actions on transition fromOperationalstate toGatherstate
5.3.2.2 Operations in theGatherstate
5.3.2.3 Events and actions on transition fromGathertoCommitstate
5.3.2.4 Operations in theCommitstate
5.3.2.5 Events and actions on transition fromCommitorRecoverytoGatherstate
5.3.2.6 Examples
EXAMPLE 5.8
EXAMPLE 5.9
5.3.3 Recovery Protocol
5.3.3.1 Event and actions on transition fromCommittoRecoverystate
5.3.3.2 Operation in theRecoverystate
5.3.3.3 Actions on transition fromRecoverytoOperationalstate
5.3.3.4 Examples
EXAMPLE 5.10
EXAMPLE 5.11
5.3.4 The Flow Control Mechanism
5.4 Vector Clock Based Group Communication System
EXAMPLE 5.12
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
EXAMPLE 6.1
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
EXAMPLE 6.2
6.4.2 Cheap Paxos
EXAMPLE 6.3
6.5 Fast Paxos
6.5.1 The Basic Steps
6.5.2 Collision Recovery, Quorum Requirement, and Value Selection Rule
EXAMPLE 6.4
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.3.1 Rejoin and Replacement
6.6.3.2 Membership Expansion
6.6.3.3 Membership Reduction
6.6.4 Limited Disk Space for Logging
REFERENCES
7. Byzantine Fault Tolerance
7.1 The Byzantine Generals Problem
7.1.1 System Model
EXAMPLE 7.1
7.1.2 The Oral Message Algorithms
EXAMPLE 7.2
EXAMPLE 7.3
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
EXAMPLE 7.4
7.3 Fast Byzantine Agreement
7.4 Speculative Byzantine Fault Tolerance
7.4.1 The Agreement Protocol
7.4.2 The View Change Protocol
EXAMPLE 7.5
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.3.1 Private key, public key, and address
8.2.3.2 Transaction
8.2.3.3 Block
8.2.4 Decentralized algorithms
EXAMPLE 8.1
8.3 Ethereum
8.3.1 Ethereum Computing Model
8.3.2 Block and Consensus
8.3.2.1 Ethereum Block Structure
8.3.2.2 Ommer Block
EXAMPLE 8.2
8.3.2.3 Ethash
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.1.1 Conflict resolution
9.4.1.2 Security of 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
WILEY END USER LICENSE AGREEMENT
