Consensus In Asynchrony: Strictly Formal
2026-07-27 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster Computing
AI summaryⓘ
The authors address a contradiction between two previous findings about how computers can agree on a decision even if some fail and messages can be delayed indefinitely. They use a very precise and formal approach to explain why earlier results seemed to disagree. Their work shows that just one step in the protocol can explain the different outcomes. Additionally, they introduce a new algorithm that can handle multiple failures and prove that it works correctly.
deterministic consensuscrash toleranceasynchronous systemsFLP impossibilityprotocol phaseformal proofdistributed algorithmscrash faults
Authors
Ivan Klianev
Abstract
In this paper, we resolve the apparent contradiction between the proven possibility of deterministic crash-tolerant consensus in a fully asynchronous environment and the reconfirmation of the FLP impossibility result by Attiya, Castañeda, and Rajsbaum. With the use of a strictly formal framework that extends their reasoning, we close this fundamental gap in theory. Specifically, we demonstrate that a single protocol phase separates their findings from reaching the exact opposite conclusion. Another important outcome is a novel algorithm with ability to tolerate multiple crash faults. We provide a rigorous, strictly formal proof of correctness to validate our results.