Wenbing Zhao - From Traditional Fault Tolerance to Blockchain

1 Cover

2 Title Page

3 Copyright

4 Dedication

5 List of Figures

6 List of Tables

7 Acknowledgments

8 Preface

9 References

10 1 Introduction 1.1 Basic Concepts and Terminologies for Dependable Computing 1.2 Means to Achieve Dependability 1.3 System Security REFERENCES

11 2 Logging and Checkpointing 2.1 System Model 2.2 Checkpoint-Based Protocols 2.3 Log Based Protocols REFERENCES

12 3 Recovery-Oriented Computing 3.1 System Model 3.2 Fault Detection and Localization 3.3 Microreboot 3.4 Overcoming Operator Errors REFERENCES

13 4 Data and Service Replication 4.1 Service Replication 4.2 Data Replication 4.3 Optimistic Replication 4.4 CAP Theorem REFERENCES

14 5 Group Communication Systems 5.1 System Model 5.2 Sequencer Based Group Communication System 5.3 Sender Based Group Communication System 5.4 Vector Clock Based Group Communication System REFERENCES

15 6 Consensus and the Paxos Algorithms 6.1 The Consensus Problem 6.2 The Paxos Algorithm 6.3 Multi-Paxos 6.4 Dynamic Paxos 6.5 Fast Paxos 6.6 Implementations of the Paxos Family Algorithms REFERENCES

16 7 Byzantine Fault Tolerance 7.1 The Byzantine Generals Problem 7.2 Practical Byzantine Fault Tolerance 7.3 Fast Byzantine Agreement 7.4 Speculative Byzantine Fault Tolerance REFERENCES

17 8 Cryptocurrency and Blockchain 8.1 History of Cryptocurrency 8.2 Bitcoin 8.3 Ethereum 8.4 Attacks on Blockchain References

18 9 Consensus Algorithms for Blockchain 9.1 Model on Blockchain Consensus 9.2 Proof of Work 9.3 Proof of Resources 9.4 Virtual Mining References

19 10 Blockchain Applications 10.1 The Value of Blockchain 10.2 Blockchain-Enabled Cyber-Physical Systems 10.3 On Blockchain Throughput 10.4 A Critical Look on Blockchain from Economy Perspective References

20 Index

21 End User License Agreement

1 Chapter 1 Figure 1.1 An example of a chain of threats with two levels of recursion. Figure 1.2 The rollback recovery is enabled by periodically taking checkpoints a... Figure 1.3 With redundant instances in the system, the failure of a replica in s... Figure 1.4 Main types of assets in a distributed system.

2 Chapter 2 Figure 2.1 An example distributed system. Figure 2.2 Consistent and inconsistent global state examples. Figure 2.3 An example of the domino effect in recovery with uncoordinated checkp... Figure 2.4 Finite state machine specification for the coordinator in the Tamir a... Figure 2.5 Finite state machine specification for the participant in the Tamir a... Figure 2.6 Normal operation of the Tamir and Sequin checkpointing protocol in an... Figure 2.7 Finite state machine specification for the Chandy and Lamport distrib... Figure 2.8 Normal operation of the Chandy and Lamport global snapshot protocol i... Figure 2.9 A comparison of the channel state definition between (a) the Chandy a... Figure 2.10 Example state intervals. Figure 2.11 An example for pessimistic logging. Figure 2.12 Transport level (a) and application level (b) reliable messaging. Figure 2.13 Optimization of pessimistic logging: (a) concurrent message logging ... Figure 2.14 Probability density function of the logging latency. Figure 2.15 A summary of the mean logging latency and mean end-to-end latency un... Figure 2.16 Probability density function of the end-to-end latency. Figure 2.17 Normal operation of the sender-based logging protocol. Figure 2.18 An example normal operation of the sender-based logging protocol. Figure 2.19 Two concurrent failures could result in the loss of determinant info...

3 Chapter 3 Figure 3.1 The three-tier architecture. Figure 3.2 The Java EE architecture. Figure 3.3 An example runtime path of an end-user request. Figure 3.4 Component class and component instances. Figure 3.5 The chi-square cumulative distribution function for degree of freedom... Figure 3.6 The path shape of the example runtime path shown in Figure 3.3.Figure 3.7 Component class and component instances.Figure 3.8 Dependency templates for nodes, processes, network paths, and the nei...Figure 3.9 A partial dependency graph for an example system.Figure 3.10 The error function.Figure 3.11 A hypothetical dependency graph with abnormality for each component ...Figure 3.12 The components that form a cycle in the f-map are reduced to a singl...Figure 3.13 The architecture of an Operator Undo framework [5, 6].

4 Chapter 4Figure 4.1 The replication algorithm is typically implemented in a fault toleran...Figure 4.2 Active replication, without (top) and with (bottom) voting at the cli...Figure 4.3 Passive replication.Figure 4.4 Semi-active replication.Figure 4.5 A write-all algorithm for data replication.Figure 4.6 The problem of the write-all-available algorithm for data replication...Figure 4.7 Preventing a transaction from accessing a not-fully-recovered replica...Figure 4.8 An example run of the quorum consensus algorithm on a single data ite...Figure 4.9 Basic steps for optimistic data replication for an operation-transfer...Figure 4.10 An example run of a system with three sites that uses Lamport clocks...Figure 4.11 An example run of a system with three sites that uses vector clocks.Figure 4.12 An example for the determination of the new version vector value aft...Figure 4.13 An example operation propagation using vector clocks in a system wit...Figure 4.14 An example for operation propagation using timestamp matrices in a s...Figure 4.15 Update commit using ack vectors in a system with three replicas.Figure 4.16 Update commit using timestamp matrices in a system with three replic...Figure 4.17 An illustration of the CAP theorem.Figure 4.18 Partition mode and partition recovery.

5 Chapter 5Figure 5.1 Examples of systems that ensure uniform total ordering and nonuniform...Figure 5.2 In the sequencer based approach, a general system is structured into ...Figure 5.3 An example rotation sequencer based system in normal operation.Figure 5.4 Normal operation of the membership view change protocol.Figure 5.5 Membership change scenario: competing originators.Figure 5.6 Membership change scenario: premature timeout.Figure 5.7 Membership change scenario: temporary network partitioning.Figure 5.8 A simplified finite state machine specification for Totem.Figure 5.9 A successful run of the Totem Membership Protocol.Figure 5.10 Membership changes due to a premature timeout by N 2.Figure 5.11 Messages sent before N 1 fails in an example scenario.Figure 5.12 Messages delivered during recovery for the example scenario.Figure 5.13 Message sent before the network partitions into two groups, one with...Figure 5.14 Messages delivered during recovery in the two different partitions f...Figure 5.15 Causal ordering using vector clocks.

6 Chapter 6Figure 6.1 Normal operation of the Paxos algorithm.Figure 6.2 A deadlock scenario with two competing proposers in the Paxos algorit...Figure 6.3 If the system has already chosen a value, the safety property for con...Figure 6.4 If two competing proposers propose concurrently, the system might end...Figure 6.5 With the promise-not-to-accept-older-proposal requirement in place, e...Figure 6.6 Normal operation of Multi-Paxos in a client-server system with 3 serv...Figure 6.7 View change algorithm for Multi-Paxos.Figure 6.8 With reconfigurations, a group of 7 replicas (initially 5 active and ...Figure 6.9 The Primary and secondary quorums formation for a system with 3 main ...Figure 6.10 The Primary and secondary quorums formation as the system reconfigur...Figure 6.11 Normal operation of Cheap Paxos in a system with 3 main replicas and...Figure 6.12 The Primary and secondary quorums formation for a system with 3 main...Figure 6.13 Normal operation of (Multi-) Fast Paxos in a client-server system.Figure 6.14 Collision recovery in an example system.Figure 6.15 Expansion of the membership by adding two replicas in method 1.Figure 6.16 Expansion of the membership by adding two replicas in method 2.Figure 6.17 Reduction of the membership by removing two replicas one after anoth...