Fault-Tolerant Message-Passing Distributed Systems: An Algorithmic Approach

Description

This book presents the most important fault-tolerant distributed programming abstractions and their associated distributed algorithms, in particular in terms of reliable communication and agreement, which lie at the heart of nearly all distributed applications. These programming abstractions, distributed objects or services, allow software designers and programmers to cope with asynchrony and the most important types of failures such as process crashes, message losses, and malicious behaviors of computing entities, widely known under the term "Byzantine fault-tolerance". The author introduces these notions in an incremental manner, starting from a clear specification, followed by algorithms which are first described intuitively and then proved correct. The book also presents impossibility results in classic distributed computing models, along with strategies, mainly failure detectors and randomization, that allow us to enrich these models. In this sense, the book constitutes an introduction to the science of distributed computing, with applications in all domains of distributed systems, such as cloud computing and blockchains. Each chapter comes with exercises and bibliographic notes to help the reader approach, understand, and master the fascinating field of fault-tolerant distributed computing. Front Matter ....Pages i-xxxi Front Matter ....Pages 1-1 A Few Definitions and Two Introductory Examples (Michel Raynal)....Pages 3-20 Front Matter ....Pages 21-21 Reliable Broadcast in the Presence of Process Crash Failures (Michel Raynal)....Pages 23-40 Reliable Broadcast in the Presence of Process Crashes and Unreliable Channels (Michel Raynal)....Pages 41-60 Reliable Broadcast in the Presence of Byzantine Processes (Michel Raynal)....Pages 61-73 Front Matter ....Pages 75-75 The Read/Write Register Abstraction (Michel Raynal)....Pages 77-94 Building Read/Write Registers Despite Asynchrony and Less than Half of Processes Crash (t < n/2) (Michel Raynal)....Pages 95-117 Circumventing the t < n/2 Read/Write Register Impossibility: the Failure Detector Approach (Michel Raynal)....Pages 119-129 A Broadcast Abstraction Suited to the Family of Read/Write Implementable Objects (Michel Raynal)....Pages 131-153 Atomic Read/Write Registers in the Presence of Byzantine Processes (Michel Raynal)....Pages 155-170 Front Matter ....Pages 171-171 Consensus and Interactive Consistency in Synchronous Systems Prone to Process Crash Failures (Michel Raynal)....Pages 173-187 Expediting Decision in Synchronous Systems Prone to Process Crash Failures (Michel Raynal)....Pages 189-213 Consensus Variants: Simultaneous Consensus and k-Set Agreement (Michel Raynal)....Pages 215-229 Non-blocking Atomic Commitment in the Presence of Process Crash Failures (Michel Raynal)....Pages 231-244 Consensus in Synchronous Systems Prone to Byzantine Process Failures (Michel Raynal)....Pages 245-267 Front Matter ....Pages 269-269 Implementable Agreement Abstractions Despite Asynchrony and a Minority of Process Crashes (Michel Raynal)....Pages 271-285 Consensus: Power and Implementability Limit in Crash-Prone Asynchronous Systems (Michel Raynal)....Pages 287-316 Implementing Consensus in Enriched Crash-Prone Asynchronous Systems (Michel Raynal)....Pages 317-351 Implementing Oracles in Asynchronous Systems Prone to Process Crash Failures (Michel Raynal)....Pages 353-383 Implementing Consensus in Enriched Byzantine Asynchronous Systems (Michel Raynal)....Pages 385-408 Front Matter ....Pages 409-409 Quorum, Signatures, and Overlays (Michel Raynal)....Pages 411-423 Back Matter ....Pages 425-459