Communication and Agreement Abstractions for Fault-Tolerant Asynchronous Distributed Systems
Author:
- Michel RaynalMRMichel Raynal
- 1 January 2010
- journal article
- Published by Springer Nature in Synthesis Lectures on Distributed Computing Theory
- Vol. 1 (1) , 1-273
Abstract
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, ...Keywords
This publication has 146 references indexed in Scilit:
- Implementing the Omega failure detector in the crash-recovery failure modelJournal of Computer and System Sciences, 2009
- The Theta-Model: achieving synchrony without clocksDistributed Computing, 2009
- On implementing omega in systems with weak reliability and synchrony assumptionsDistributed Computing, 2008
- A Timing Assumption and Two t-Resilient Protocols for Implementing an Eventual Leader Service in Asynchronous Shared Memory SystemsAlgorithmica, 2008
- The information structure of indulgent consensusIEEE Transactions on Computers, 2004
- Disk PaxosDistributed Computing, 2003
- A simple proof of the uniform consensus synchronous lower boundInformation Processing Letters, 2003
- A simple bivalency proof that t-resilient consensus requires t+1 roundsInformation Processing Letters, 1999
- Byzantine quorum systemsDistributed Computing, 1998
- Fault-tolerance and self-stabilization: impossibility results and solutions using self-stabilizing failure detectorsInternational Journal of Systems Science, 1997