# Distributed Consensus: Beating Impossibility with Probability One

DevFeed: [Distributed Consensus: Beating Impossibility with Probability One](<https://devfeed.tech/articles/distributed-consensus-beating-impossibility-with-probability-one-12452.md>)

Original publisher: [Read original article](<http://brooker.co.za/blog/2014/01/12/ben-or.html>)

Author: Marc Brooker

Published: 2014-01-12T00:00:00Z

Content type: article

Language: en

Sources: [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog.md>), [Marc Brooker's Blog](<https://devfeed.tech/sources/marc-brooker-s-blog-2.md>)

Topics: [distributed-systems](<https://devfeed.tech/topics/distributed-systems.md>), [systems](<https://devfeed.tech/topics/systems.md>), [Algorithm](<https://devfeed.tech/topics/algorithm.md>)

Tags: [distributed-systems](<https://devfeed.tech/tags/distributed-systems.md>), [practitioner](<https://devfeed.tech/tags/practitioner.md>), [research](<https://devfeed.tech/tags/research.md>), [systems](<https://devfeed.tech/tags/systems.md>)

## AI overview

The article explains why impossibility proofs matter in distributed systems and how clearly defined system models can reveal ways to work around them. It highlights Ben-Or's randomized consensus algorithm, which achieves consensus with probability one in a slightly modified asynchronous message-passing model.

## Source excerpt

Distributed Consensus: Beating Impossibility with Probability One Distributed systems models are critical to understanding impossibility results Reading Nancy Lynch's 1989 paper A Hundred Impossibility Proofs for Distributed Computing was the first time I came to a real understanding of the value of impossibility proofs. Before reading it, I was aware of many of the famous impossibility proofs, including Brewer's CAP Theorem, FLP impossibility and the lower bounds of number of rounds needed for consensus, but I'd always held existence proofs to be somehow more important. My attitude was along these lines: What good are impossibility results, anyway? They don't seem very useful at first, since they don't allow computers to do anything they couldn't previously. Following that question (in Section 3.5 of A Hundred Impossibility Proofs), Lynch goes on to justify the importance of impossibility proofs. The whole case is worth reading, but the one that resonates with me most strongly as a practitioner is: ... the effect of the impossibility result might be to make a systems developer clarify his/her claims about what the system accomplishes. Nearly 25 years have passed since the publication of this paper, and that remains something of a hopeful dream. Despite the efforts of Lynch, Lamport, Aphyr, Daniel Abadi and many others, there's still a long way to go in having distributed systems developers clearly state the guarantees their systems are making. Another effect of impossibility proofs, and the clear definition of the models in which they exist, has been research into how little it is possible to change the model to get around the impossibility result. Easily my personal favorite result in this area is another paper from the 1980s, Michael Ben-Or's Another Advantage of Free Choice: Completely Asynchronous Agreement Protocols from 1983 (sadly, I can't seem to find an open-access version of that paper), and a similar result by Rabin in the same year. Ben-Or looked at the F