Randomized consensus: agreeing by flipping coins (Ben-Or 1983)

Michael Ben-Or showed that asynchronous processes can reach agreement despite crashes if they may flip coins. In each round they exchange values, propose any value held by a strict majority, and adopt a proposal they see, or flip a coin if they see none. A decision follows once enough processes propose the same value.

Against a scheduler that delivers messages to keep processes split, the protocol still decides: eventually the coins all land the same way. The number of rounds is random, with an exponential tail.

import matplotlib.pyplot as plt

import blockchainkit as bk

Decide despite an adversarial scheduler

run = bk.consensus.ben_or([0, 0, 1, 1], faults=1, seed=1983)
assert run.decided and len(set(run.decisions.values())) == 1
print(f"decided {set(run.decisions.values())} after {run.rounds} rounds")

decided {1} after 3 rounds

Unanimous inputs decide in one round

assert bk.consensus.ben_or([1, 1, 1, 1], faults=1).rounds == 1

How many rounds?

rounds = [bk.consensus.ben_or([0, 0, 1, 1], faults=1, seed=s).rounds for s in range(400)]
assert all(bk.consensus.ben_or([0, 1, 0, 1], faults=1, seed=s).decided for s in range(50))
fig, ax = plt.subplots(figsize=(7, 3.5))
ax.hist(rounds, bins=range(1, max(rounds) + 2), color="#2563eb", edgecolor="white")
ax.axvline(sum(rounds) / len(rounds), color="black", linestyle="--", label="mean")
ax.set(
    xlabel="rounds to decide (4 processes, adversarial delivery)",
    ylabel="runs",
    title="Termination with probability one",
)
ax.legend()
fig.tight_layout()

plt.show()

Exercise

The adversary here stalls unless all four coins agree, which happens with probability 2/16 per round. Derive the expected number of rounds and compare it with the histogram’s mean.

A worked solution is in Exercises: consensus.