Details

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

<p><b>Dr. Zhao</b> 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.</p>

<p><b>A critical book that reveals important features of the blockchain technology</b></p><p>The 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.</p><p>It 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 people even rank it at the same level of the Internet. The book also expresses a grave concern over using traditional consensus algorithms in blockchain because the primary benefits of using blockchain, such as decentralization and immutability, could be lost under cyberattacks.</p><p>This groundbreaking book:</p><ul><li>Elaborates why blockchain consensus algorithms are transformational in solving the distributed consensus problem;</li><li>Provides a detailed explanation on how Bitcoin and Ethereum Proof-of-Work consensus algorithms work;</li><li>Presents a critical look on the current state of Proof-of-Stake consensus algorithms and provides a much needed document on the first practical implementation of the Proof-of-Stake algorithm used in PeerCoin;</li><li>Formulates a taxonomy on blockchain benefits, identified key operations in applications that could benefit from using blockchain;</li><li>Introduces the foundation for dependent distributed computing so that one could appreciate the impact of the blockchain technology.</li></ul><p><b>Audience</b></p><p>Software developers and researchers who work with blockchain technology and those who wish to develop secure and dependable systems.</p>

US