FLP: no deterministic consensus in an asynchronous network (1985)

Fischer, Lynch and Paterson proved that no deterministic protocol can always reach agreement in an asynchronous system where even one process may crash. The adversary does not need to crash anyone: it only chooses the order in which messages arrive, and can keep the system undecided forever.

What to look for

Ben-Or’s protocol with its coin replaced by a fixed rule, here “process p adopts p mod 2”, never decides against a scheduler that keeps every process from seeing a strict majority: the values stay split two against two in every round. Give the processes real coins and the same scheduler loses. FLP says every deterministic protocol has some such schedule. Practical protocols escape it with randomness (Ben-Or) or timing assumptions (partial synchrony).

The history behind this experiment: Breakthroughs in Consensus.

A deterministic protocol, stalled forever

import matplotlib.pyplot as plt

import blockchainkit as bk


def parity(process, round_):
    return process % 2


stalled = bk.consensus.ben_or([0, 0, 1, 1], faults=1, coin=parity, max_rounds=500)
assert not stalled.decided and stalled.rounds == 500
print("adversarial schedule, deterministic rule: no decision after 500 rounds")

adversarial schedule, deterministic rule: no decision after 500 rounds

Change one ingredient at a time

cases = {
    "deterministic rule": bk.consensus.ben_or([0, 0, 1, 1], faults=1, coin=parity, max_rounds=500),
    "random coin": bk.consensus.ben_or([0, 0, 1, 1], faults=1, seed=3, max_rounds=500),
}
for label, run in cases.items():
    print(label, "->", "decided" if run.decided else "stalled", f"({run.rounds} rounds)")
assert [run.decided for run in cases.values()] == [False, True]
fig, ax = plt.subplots(figsize=(7, 3.2))
ax.bar(cases.keys(), [run.rounds for run in cases.values()], color=["#dc2626", "#16a34a"])
ax.set(
    ylabel="rounds run (500 = gave up)", title="Same adversarial schedule, deterministic vs random"
)
fig.tight_layout()

deterministic rule -> stalled (500 rounds)
random coin -> decided (21 rounds)

Exercise

Try coin=lambda p, r: r % 2 (every process adopts the same bit). It decides against this scheduler. Why does that not contradict FLP? (The theorem promises a stalling schedule for every deterministic protocol, not that this particular scheduler finds it.)