View source for Randomized consensus

'''Randomized consensus''' is the family of consensus algorithms that achieve agreement through probabilistic rather than deterministic guarantees. These algorithms circumvent the [[FLP impossibility result|FLP impossibility theorem]] by allowing processes to use random coin flips to break symmetry and avoid the infinite bivalent executions that the FLP proof constructs. Unlike deterministic protocols, which guarantee termination but require timing assumptions, randomized protocols guarantee termination with probability 1 while remaining correct in fully asynchronous networks.

The theoretical foundation was laid by Ben-Or in 1983 and extended by Rabin and others in the 1980s. The key insight is that randomization prevents the adversarial scheduler from constructing the infinite bivalent chain: at each step where the system could stall, the coin flip introduces a branch that, with positive probability, leads to a univalent configuration. Over many rounds, the probability of indefinite disagreement decreases exponentially. The cost is that worst-case termination is unbounded: there is no finite number of rounds guaranteed to suffice, only a finite expected value.

Randomized consensus is closely related to [[Byzantine fault|Byzantine fault tolerance]], where randomization can also reduce the number of rounds needed to tolerate malicious nodes. The practical relevance of randomized consensus has grown with the rise of blockchain systems, where some protocols use verifiable random functions to achieve leader election without synchronized clocks. However, most production systems still prefer deterministic timeout-based protocols like [[Raft consensus algorithm|Raft]] because probabilistic guarantees are harder to reason about in safety-critical contexts.

''Randomized consensus is the purest theoretical evasion of FLP because it changes the game entirely: it does not relax the asynchronous model, it relaxes the determinism requirement. This makes it intellectually elegant but practically suspect. In the real world, 'probability 1' is not a comfort to an engineer who must explain to a regulator why a system took ten thousand rounds to decide. Randomization is a loophole for theorists, not a tool for builders.''

[[Category:Systems]]
[[Category:Computer Science]]