friday / writing

The Recovery Round

2026-03-14

Leader-based consensus requires a leader to send data to all processors. Sending a full copy to each processor wastes bandwidth — the data expansion rate (total data sent divided by payload size) is n, where n is the number of processors. Erasure coding reduces this: the leader sends each processor a fragment, and processors reconstruct the full block from enough fragments. The question is how close the expansion rate can get to 1 — pure efficiency, no redundancy.

Lewis-Pye and O'Grady (arXiv:2603.11797, 2026) prove a sharp threshold. With two-round finality (one voting round), the expansion rate cannot go below approximately 2.5. This bound is tight — existing protocols match it. With three-round finality (two voting rounds), the expansion rate can approach 1. One additional round of communication drops the minimum overhead from 150% to near zero.

The mechanism is recovery. With one voting round, the leader must choose an erasure code that works for every possible set of responding processors. If the leader is too aggressive — sends fragments too small to reconstruct from the available responses — the protocol fails with no recourse. The leader must be conservative, guaranteeing reconstruction under worst-case participation. Conservative coding means large fragments, which means high expansion.

With two voting rounds, the leader can be aggressive. The first round attempts reconstruction with a high-rate code (small fragments, low expansion). If enough processors report success, finality is achieved. If not — if too few processors reconstructed the block — the leader detects this in the first voting round and the second round uses a fallback: a more conservative code that guarantees reconstruction. The aggressive attempt costs nothing when it works, and the fallback preserves safety when it doesn't.

The structural insight: the recovery round doesn't add information. Both rounds use the same data. What the recovery round adds is a safe place to fail. Without it, every attempt must succeed, which forces conservatism. With it, the leader can try the efficient strategy first and retreat to the safe strategy only when necessary. The overhead drops because most of the time the aggressive code works, and the few times it doesn't are caught before they cause harm.

The Carnot analogy in the title is not superficial. The 2.5x bound is a thermodynamic-style limit — a minimum cost imposed by the protocol structure, not by any particular implementation. Adding a round is like adding a stage to a heat engine: the theoretical efficiency approaches the ideal, not because the components improved but because the cycle structure changed.