Adaptive Consensus in Large-Scale Distributed Systems: Beyond Static Fault Models — Epoche C2
The design under examination, stated precisely A Byzantine fault-tolerant replication protocol built to the standard recipe — $n$ replicas of which at most $f$ may deviate arbitrarily and in concert, the failure mode Lamport, Shostak and Pease named Byzantine in 1982 when they proved that three generals cannot agree if one of them is a traitor and that unauthenticated agreement requires more than $3f$ participants in general, with $n \ge 3f+1$ — sends the same number of messages to commit a request on a quiet afternoon as it does while a third of its membership is actively lying. This essay is about whether that invariance is a defect worth engineering away, and about which parts of such a protocol may be made responsive to observed conditions without destroying the guarantee that justified building it. The answer is that a good deal may be adapted, that the throughput gains available are large and have already been realised, and that the one adaptation the original version of this essay recommended most warmly — tuning the resilience threshold to an estimated fault probability — is the one that cannot be recommended at all. Begin with the quantity everything else is measured against. The bound $n \ge 3f+1$ is not a convention; it falls out of two requirements in three lines. First, the protocol must be able to make progress when $f$ replicas never answer, since it cannot tell a silent Byzantine replica from a crashed one, so the number of responses a decision waits for — its quorum size $q$ — satisfies $q \le n-f$. Second, any two quorums must overlap in at least one correct replica, or two conflicting values could each collect a quorum and the protocol would decide twice. Two sets of size $q$ drawn from $n$ elements intersect in at least $2q-n$ elements, and to guarantee a correct replica in that intersection the overlap must exceed the number of faulty replicas: $2q-n \ge f+1$. Substituting the first constraint into the second gives $2(n-f)-n \ge f+1$, that is $n-2f \ge f+1$, that is $n \ge 3f+1$. Dwork, Lynch and Stockmeyer proved in 1988 that this is tight for the partially synchronous model — the model in which message delay is bounded by some $\Delta$ that either is unknown, or holds only after an unknown time — and that under full asynchrony no deterministic protocol solves the problem at all. The threshold is therefore a theorem about the network model, not a safety margin chosen by an engineer, and this matters for everything that follows. Where the quadratic cost actually comes from Having fixed the threshold, the cost of a decision can be counted rather than asserted. Castro and Liskov's Practical Byzantine Fault Tolerance, published in 1999, commits a request in three message rounds. The primary multicasts a pre-prepare to the $n-1$ backups; each backup multicasts a prepare to the other $n-1$ replicas; each of the $n$ replicas then multicasts a commit to the other $n-1$. Summing, the protocol sends $$(n-1) + (n-1)^2 + n(n-1) = (n-1)\bigl(1 + (n-1) + n\bigr) = 2n(n-1)$$ messages per decision, which for a hundred replicas is $2 \times 100 \times 99 = 19\,800$. The exponent is two and not one because two of the three rounds are all-to-all: every replica must convince every other replica that it saw a quorum, and with no way to aggregate those attestations each must be delivered and verified individually. That is the whole source of the quadratic, and naming it that precisely tells us where to look for a remedy. The remedy that works turns out to require no probabilistic reasoning whatsoever. HotStuff, published by Yin, Malkhi, Reiter, Gueta and Abraham in 2019, replaces the all-to-all rounds with a star: replicas send their votes only to the current leader, who combines $n-f$ partial signatures into a single threshold signature that certifies the quorum and can be verified in constant time by anyone. A quorum certificate of that kind is as convincing as the $n-f$ separate votes it summarises, so the second all-to-all round disappears. Both protocols organise their work into views — a view is one attempt to reach a decision under one designated leader, abandoned for the next view when that leader is suspected of having failed — and the changeover is where the earlier design is most expensive. Basic HotStuff runs four phases per view, each consisting of one leader broadcast and one round of votes back, giving $8(n-1)$ messages per decision: $792$ at $n = 100$, a factor of $25$ below the count above, with the chained variant amortising further by pipelining one phase per view. The price is real and should be stated: a fourth phase is added to the three of the earlier protocol, so latency in the common case rises, and the leader now sends $4(n-1)$ messages where a PBFT replica sends $2(n-1)$, concentrating load on one node that leadership rotation must then spread. What is bought is linearity in the number of authenticators — the individual signatures and message authentication codes in which cryptographic verification cost is counted — in the view change as well as the common case, against the cubic authenticator cost of the earlier protocol's view change. What the lower bound actually forbids The original version of this essay appealed to an "information-theoretic lower bound" without saying which one, and the vagueness concealed the argument's most important step. There are two relevant bounds and neither says what the appeal wanted. Dolev and Reischuk proved in 1985 that any deterministic protocol solving Byzantine agreement must, in some execution, send $\Omega(f^2)$ messages. The shape of the argument is a starvation construction: if the total message traffic is small, then many correct processes receive very few messages, and the adversary can pick a set of faulty processes that stay silent towards exactly those, leaving them unable to distinguish an execution in which the decision is $0$ from one in which it is $1$. Fischer and Lynch proved in 1982 that any deterministic sy