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.

What to look for

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.

The history behind this experiment: Breakthroughs in Consensus. See Exercises: consensus for a worked solution to the exercise.

Decide despite an adversarial scheduler

import matplotlib.pyplot as plt

import blockchainkit as bk

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()

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.