Communication and Agreement Abstractions for Fault-tolerant Asynchronous Distributed Systems
Understanding distributed computing is not an easy task. This is due to the many facets of uncertainty one has to cope with and master in order to produce correct distributed software. Considering the uncertainty created by asynchrony and process crash failures in the context of message-passing systems, the book focuses on the main abstractions that one has to understand and master in order to be able to produce software with guaranteed properties. These fundamental abstractions are communication abstractions that allow the processes to communicate consistently (namely the register abstraction and the reliable broadcast abstraction), and the consensus agreement abstractions that allows them to cooperate despite failures. As they give a precise meaning to the words "communicate" and "agree" despite asynchrony and failures, these abstractions allow distributed programs to be designed with properties that can be stated and proved. Impossibility results are associated with these abstractions. Hence, in order to circumvent these impossibilities, the book relies on the failure detector approach, and, consequently, that approach to fault-tolerance is central to the book. Table of Contents: List of Figures / The Atomic Register Abstraction / Implementing an Atomic Register in a Crash-Prone Asynchronous System / The Uniform Reliable Broadcast Abstraction / Uniform Reliable Broadcast Abstraction Despite Unreliable Channels / The Consensus Abstraction / Consensus Algorithms for Asynchronous Systems Enriched with Various Failure Detectors / Constructing Failure Detectors
What people are saying - Write a review
We haven't found any reviews in the usual places.
Other editions - View all
algorithm described application message AS_Fn,t ASn,t ASn,t[t assumption asynchronous systems atomic commit atomic register binary consensus block forever claim C1 CO-broadcast CO-delivered code for pi completeness property consensus algorithm consensus object consensus problem construction correct process Correct(F deﬁned deﬁnition denoted described in Figure Distributed Computing End of proof est1i est2i executes failure detector class failure pattern fair channel faulty process FIFO ﬁnite follows global heartbeat Hence implemented inﬁnite number invokes Lemma Let us ﬁrst local variable message delivery message msg non-faulty process number of processes perfect failure detector pi receives pi to pj predicate process crashes process decides process identities process pi Proof of claim protocol messages R.read random oracle rec_byi[m receives a message round-trip delay satisﬁed sequence number solved speciﬁcation suspectedi system model termination property Theorem TO-URB total order underlying uniform reliable broadcast URB abstraction URB-broadcast URB-delivered validity property variables wait