Symptom

A node in your cluster is not down. It is worse than down.

Its disk is returning corrupted blocks that pass the checksum because the checksum is corrupted too. Or a NIC with a firmware bug is duplicating and reordering frames. Or a bad memory module flipped a bit in a config value and the node now believes it owns a shard it does not. Or someone has root on one machine.

Every failure model you have used so far assumes nodes stop cleanly. FLP (T062) assumes crash faults. Raft assumes crash faults. Your health checks assume a sick node goes quiet. This node is not quiet. It is actively saying wrong things, confidently, to different peers, possibly saying different wrong things to different peers.

The operational signature is distinctive: the cluster disagrees about what happened, every node’s logs are internally consistent, and no two nodes’ logs agree. There is no crash to point at. And a majority vote does not save you, because the faulty node votes too.

Statement

A commanding general must send an order — attack or retreat — to $n-1$ lieutenants. Some generals, possibly including the commander, are traitors who may say anything to anyone, including different things to different people.

The protocol must guarantee:

  • IC1. All loyal lieutenants obey the same order.
  • IC2. If the commander is loyal, every loyal lieutenant obeys the commander’s order.

With $f$ traitors, a solution using oral messages exists if and only if there are at least $3f+1$ generals.

Byzantine agreement among $n$ processes tolerating $f$ arbitrary faults is solvable with unauthenticated messages if and only if $n \ge 3f+1$. With unforgeable signatures, the bound relaxes to $n \ge f+1$ for agreement, and $n \ge 2f+1$ when combined with a liveness requirement in the usual partially synchronous setting.

Both directions matter. There is a protocol at $3f+1$, and there is no protocol at $3f$. The bound is tight, so this is not a limit of current technique.

Concretely: tolerating one liar takes four nodes, two takes seven, three takes ten. Not three, six, and nine. The extra node in each case is the entire content of the theorem.

Argument

The impossibility, for $n=3$, $f=1$. This case carries the whole idea.

Three generals: commander $C$ and lieutenants $L_1$, $L_2$. Exactly one may be a traitor. Consider two scenarios.

Scenario A. $C$ is loyal and sends “attack” to both. $L_2$ is a traitor. $L_1$ receives “attack” from $C$, and then receives from $L_2$ the report “the commander told me retreat.” $L_1$ sees a disagreement and knows one of $C$ or $L_2$ is lying, but not which.

Scenario B. $C$ is the traitor, sending “attack” to $L_1$ and “retreat” to $L_2$. $L_2$ is loyal and truthfully reports “the commander told me retreat.”

Now look at what $L_1$ actually received. In both scenarios: “attack” from the commander, and “$L_2$ says the commander told me retreat.” The two scenarios are indistinguishable to $L_1$. Every bit it has is identical.

So $L_1$ must act the same way in both. In Scenario A, IC2 forces $L_1$ to attack, since the commander is loyal. So $L_1$ attacks in Scenario B too.

Apply the mirror argument to $L_2$ in the scenario where $C$ is loyal and sends “retreat,” with $L_1$ as the traitor. By symmetry, $L_2$ retreats in Scenario B.

But Scenario B has both lieutenants loyal, and they have done different things. IC1 is violated, and no protocol avoids it, because the violation came from indistinguishability rather than from any choice the protocol made. $\blacksquare$

Why the general bound is $3f+1$. The scaling argument is a simulation. If a protocol existed for $n \le 3f$, partition the generals into three groups of at most $f$ each and have three “super-generals” each simulate one group. A single traitorous super-general corresponds to at most $f$ real traitors, which the hypothetical protocol tolerates — and you have solved the three-general problem with one traitor, which we just proved impossible.

Where the number comes from, intuitively. You have $n$ nodes and $f$ are lying. To reach a decision, you must be able to gather a quorum whose honest members alone are a majority of the honest nodes, while also allowing that $f$ nodes may be unreachable. You wait for $n-f$ responses, since $f$ may never answer. Of those $n-f$, up to $f$ may be lies, leaving $n-2f$ honest. For the honest votes to outnumber the lies you need $n - 2f > f$, so $n > 3f$. Each $f$ is subtracted for a distinct reason — the ones you cannot wait for, and the ones who lie to you — and the third comes from needing a strict majority among the remainder.

The signature escape. The impossibility rests on $L_1$ being unable to verify $L_2$’s claim about what $C$ said. Give every general an unforgeable signature, and $L_2$ must produce $C$’s signed order. A traitorous $L_2$ cannot fabricate one, and a traitorous $C$ that signs two contradictory orders produces a transferable proof of its own treachery. The bound collapses to $n \ge f+1$ for agreement alone. This is why blockchains, which have signatures by construction, work with quorums that would otherwise be impossible, and why PBFT-family protocols still use $3f+1$: they want liveness under partial synchrony, not just agreement.

Forbids

Byzantine fault tolerance in a three-node cluster. A three-node etcd or ZooKeeper survives one crash. It does not survive one node lying, and the distinction is invisible in normal operation and total when it matters.

Majority voting as a Byzantine defence. With $f$ liars among $2f+1$ nodes, a “majority” of $f+1$ can consist of $f$ liars plus one honest node. The vote returns a wrong answer with full confidence.

Detecting a Byzantine node from its behaviour alone in a general system. A node that lies consistently and plausibly is indistinguishable from a node that is correct in a different scenario. That is exactly the indistinguishability the proof used.

Unauthenticated agreement at $n \le 3f$, unconditionally. No cleverness, no extra rounds, no better cryptographic hash.

Does not forbid

It does not mean you need BFT, and this is the misreading that wastes the most engineering effort. Byzantine fault tolerance costs $O(n^2)$ messages per decision — a 100-node PBFT cluster exchanges 10,000 messages to agree on one value — and it is the right tool only when you genuinely have mutually distrusting parties. Google, Amazon, and Meta run planetary infrastructure on crash-fault-tolerant consensus. Inside a trusted datacenter the realistic Byzantine faults are corruption and bugs, and those are handled far more cheaply by checksums, ECC memory, and end-to-end verification than by a consensus protocol. Bitcoin, Ethereum, Tendermint, and Diem need BFT because their participants are strangers, and that is the actual criterion.

It does not forbid tolerating more than $n/3$ failures when they are not Byzantine. A protocol can tolerate $f$ Byzantine faults and additional crash faults simultaneously under hybrid fault models, because crashes are a strictly easier failure to survive.

It does not apply to synchronous systems with signatures. With both, Dolev and Strong showed agreement is possible with any $n > f$, in $f+1$ rounds. The $3f+1$ bound is specifically the price of asynchrony without authentication, and stating it without those qualifiers is how it gets misapplied.

It does not mean cheap defences are worthless, which is the practical point most teams miss. Most real “Byzantine” faults in a datacenter are not adversarial. ZFS and Btrfs checksums catch silent disk corruption. ECC memory catches bit flips. TLS catches on-path tampering. Amazon’s S3 does end-to-end checksums across every hop. Each of these eliminates a class of arbitrary fault at a fraction of BFT’s cost, and stacking them is why crash-fault-tolerant systems work in practice despite hardware being imperfect.

It does not say the faulty node must be malicious. “Byzantine” means arbitrary, not hostile. A memory-corrupted node with no attacker anywhere near it is Byzantine in the technical sense, and this is the far more common case. Treating the model as being about attackers causes people to dismiss it in environments where it genuinely applies.

Boundary

The $3f+1$ bound holds for asynchronous or partially synchronous systems without authentication. Each assumption you relax moves the bound:

  • Add signatures. $n \ge f+1$ for agreement with synchrony; $n \ge 2f+1$ in the partially synchronous protocols people actually deploy. Signatures are cheap now, which is why every modern BFT protocol assumes them.
  • Add synchrony. Dolev-Strong reaches agreement in $f+1$ rounds with any $n > f$, given signatures and a known message-delay bound.
  • Add randomization. Randomized BFT protocols circumvent FLP’s termination problem the same way crash-fault protocols do, without changing the $3f+1$ resilience bound.
  • Weaken the requirement. Bitcoin does not achieve agreement in this sense at all. It achieves eventual probabilistic agreement under an honest-majority hashpower assumption, which is a different theorem with a different bound, and the confirmation-depth convention exists precisely because the guarantee is probabilistic.

What remains true throughout: the price of arbitrary faults is at least one extra node per fault beyond what crashes cost, and that extra node is buying you the ability to tell a liar from a silence. Whether you should pay it is a question about your trust boundary, not your uptime target.