### Conditions on input vectors for consensus solvability in asynchronous distributed systemsConditions on input vectors for consensus solvability in asynchronous distributed systems

Access Restriction
Subscribed

 Author Mostefaoui, Achour ♦ Rajsbaum, Sergio ♦ Raynal, Michel Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2003 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Asynchronous systems ♦ Atomic registers ♦ Consensus problem ♦ Crash failures ♦ Fault-tolerance ♦ Message-passing ♦ Shared memory Abstract This article introduces and explores the $\textit{condition-based}$ approach to solve the consensus problem in asynchronous systems. The approach studies $\textit{conditions}$ that identify sets of input vectors for which it is possible to solve consensus despite the occurrence of up to $\textit{f}$ process crashes. The first main result defines $\textit{acceptable}$ conditions and shows that these are exactly the conditions for which a consensus protocol exists. Two examples of realistic acceptable conditions are presented, and proved to be maximal, in the sense that they cannot be extended and remain acceptable. The second main result is a generic consensus shared-memory protocol for any acceptable condition. The protocol always guarantees agreement and validity, and terminates (at least) when the inputs satisfy the condition with which the protocol has been instantiated, or when there are no crashes. An efficient version of the protocol is then designed for the message passing model that works when $\textit{f}$ < $\textit{n}/2,$ and it is shown that no such protocol exists when $\textit{f}$ ≥ $\textit{n}/2.$ It is also shown how the protocol's safety can be traded for its liveness. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2003-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 50 Issue Number 6 Page Count 33 Starting Page 922 Ending Page 954

#### Open content in new tab

Source: ACM Digital Library