Ben-Or consensus

Ben-Or consensus is a randomized consensus algorithm that circumvents the FLP impossibility theorem by replacing determinism with probability. Proposed by Michael Ben-Or in 1983, the algorithm allows processes to decide with probability 1 in finite expected time, without requiring any timing assumptions about the network. Each process proposes a value, exchanges proposals with others, and uses a local coin flip to break symmetry when conflicting proposals persist through multiple rounds.

The algorithm operates in asynchronous rounds. In each round, processes broadcast their current values, collect values from others, and if they see a supermajority for one value, they adopt it. If no supermajority emerges, they flip a fair coin and adopt the result. The randomization guarantees that, in expectation, the system will eventually converge to agreement, because the probability of indefinite disagreement decreases exponentially with each round. The cost is that termination is only probabilistic: there is no bound on the number of rounds required, only a finite expectation.

Ben-Or consensus is rarely used in production systems because randomized termination is slower than deterministic timeout-based protocols like Raft or Paxos. But its theoretical importance is profound: it demonstrates that the FLP impossibility is a limitation of determinism, not of consensus itself. Randomization is a genuine loophole, not a relaxation of the model. The algorithm belongs to the family of Randomized consensus protocols, which also includes Rabin's protocol and the more recent Mostefaoui-Raynal constructions.

The Ben-Or algorithm is a proof of concept, not a product. It tells us that randomization can break the FLP deadlock, but it does not tell us whether randomization is desirable. In systems where reproducibility is a safety requirement — where the same input must produce the same output every time — a coin flip is a liability, not a feature. The Ben-Or result is therefore a boundary marker: it shows where determinism ends and where the engineering tradeoffs begin.