Skip to content

Randomized Common-Coin Protocol

Randomized asynchronous agreement protocol — instantiates Assumption-Bounded Distributed Agreement

Guarantees agreement will actually terminate under full asynchrony — where deterministic protocols provably cannot — by having undecided participants fall back on a shared, unpredictable coin instead of a timeout they can never trust.

The FLP impossibility result says that in a fully asynchronous network with even one crash, no deterministic protocol can guarantee both safety and termination — because a slow participant is forever indistinguishable from a dead one, and any protocol that waits can be scheduled into waiting forever. Randomized Common-Coin Protocol is the family that escapes this without smuggling in a timing assumption. Its defining move is to break symmetry with shared randomness: when a voting round ends inconclusively, every correct participant consults a common coin — a value no participant (or adversary) can predict in advance, yet all correct participants compute identically — and adopts it as the next round's estimate. Because the adversary cannot steer the schedule to dodge a coin it cannot foresee, the probability of remaining undecided halves each round and drives to zero. Safety and validity hold in every round unconditionally; only liveness is made probabilistic. It is the protocol you select precisely when no synchrony can be assumed at all.

Example

A permissioned ledger is run jointly by a dozen banks on several continents, over public internet links whose latency is wildly variable and possibly adversarially delayed. A partial-synchrony BFT protocol would keep timing out and changing leaders during bad network spells, stalling settlement. The consortium instead runs an asynchronous, common-coin protocol in the tradition of HoneyBadgerBFT: each epoch, every bank proposes a batch of transactions, the replicas run a randomized agreement per batch, and whenever a round cannot yet decide, they draw a common coin — realized from threshold-signature shares that only combine into an unpredictable value once enough banks contribute. No matter how the network reorders or delays messages, agreement finalizes in an expected handful of rounds, because the adversary cannot predict the coin to keep the banks apart. Throughput is steady even when latency is not — the protocol never waits on a clock, so a slow link cannot masquerade as a failure and freeze it.[1]

How it works

  • Vote, and decide only on a clear super-quorum. Each round, if a large enough quorum already agrees, the value is decided and locked in; safety never depends on the coin.
  • Fall back on the coin when stuck. If the round is inconclusive, correct participants adopt the common coin's value as their next estimate, so a fresh, unbiased split is attempted rather than an endless wait.
  • Make the coin unpredictable-yet-shared. The coin is built so that no coalition can compute it early (defeating an adversarial scheduler) but all correct participants derive the same value (so they converge) — typically via threshold cryptography.
  • Terminate in expectation. The chance of still being undecided decays geometrically, giving termination with probability 1 in an expected constant number of rounds.

Tuning parameters

  • Coin construction — independent local coins (no setup, but expected exponentially many rounds) versus a shared cryptographic common coin (expected constant rounds, at the cost of a distributed key setup). This is the dial that sets both cost and speed.
  • Fault threshold — the tolerated f against n (for asynchronous Byzantine agreement, n ≥ 3f + 1). Every extra tolerated fault costs replicas and messages.
  • Batch size — how many values are agreed per epoch. Larger batches amortize the per-round overhead of asynchrony but raise latency for any single item.
  • Adversary assumption for the coin — how strong a scheduler and computational adversary the coin must resist. Stronger assumptions buy tighter round bounds but rest on heavier cryptography.

When it helps, and when it misleads

Its strength is singular: it is the way to guarantee that agreement terminates when you genuinely cannot assume any bound on message delay — including when an adversary controls scheduling. It needs no timeout tuning, and it cannot be frozen by the "is-it-slow-or-dead?" ambiguity that stalls timeout-based protocols.

Its costs are equally specific. "Terminates with probability 1" is an expected-time, not a bounded-time, guarantee — a run can be long, only with vanishing probability — so it is wrong for hard-real-time deadlines. Each round is more expensive (extra messages and cryptography) than a leader-based step, so in the common case of a well-behaved, partially-synchronous network a simple leader protocol is far cheaper. The shared coin usually needs a trusted or distributed key setup, which becomes its own attack surface. The classic misuse is paying asynchronous prices for a synchronous network — deploying it where partial synchrony holds and a leader-based protocol would do — or trusting the coin's setup without scrutiny. The discipline is to reserve it for the genuinely-asynchronous or adversarially-scheduled case, and to read its liveness guarantee as an expectation, never a deadline.

How it implements the components

  • coordination_protocol_selection_rule — it is the asynchronous branch of the choice: when the assumption budget forbids any timing bound, this randomized family is what you select over a leader-and-timeout protocol.
  • termination_condition — its signature contribution: termination with probability 1 in expected constant rounds, replacing "reach a quorum or keep waiting" with a randomized guarantee that the undecided probability decays to zero.
  • validity_rule — every round preserves the agreement's validity predicate (a decided value was legitimately proposed by a correct participant); the coin influences which value and when, never legitimacy.

It does not authenticate messages or set the Byzantine budget (fault_model, identity_or_credential_signal → Byzantine Fault-Tolerant Quorum Protocol), maintain an ordered log (state_consistency_guard → Raft-Style Replicated-Log Protocol), or elect a leader — it deliberately has none, in contrast to Term/Epoch Leader Election.

Notes

The guarantee is genuinely probabilistic and it is easy to mis-sell: safety and validity hold always, but termination holds only with probability 1, meaning "eventually, almost surely" — not "by a deadline." Confusing that expected-time guarantee for a worst-case bound is the trap. This is the honest form of coexisting with FLP: rather than assuming synchrony (as timeout-based protocols do), it trades a deterministic termination time for a guaranteed termination event.

References

[1] Randomized consensus escapes the FLP impossibility by using randomness instead of timing; Ben-Or's protocol and Rabin's common-coin construction are the classical results, and later work (for example Cachin–Kursawe–Shoup and the HoneyBadgerBFT system) builds practical asynchronous Byzantine agreement on a shared cryptographic coin. It is cited as a genuine line of work, not for any specific benchmarked figure. ↩