Byzantine Fault Tolerance: Know Your Failure Model First

By Sergey Nosov

16 October 2026

On 13 May 2008, Space Shuttle Discovery was being loaded with propellant for mission STS-124. Then one of the four general-purpose computers (GPCs) in its redundant set disagreed with the other three. As programmed, the computers’ fault detection, isolation, and recovery (FDIR) logic voted it out. Three seconds later, a second computer disagreed, and propellant loading stopped. During troubleshooting, the last two disagreed with each other. A NASA write-up calls the result “a complete system disagreement” and adds: “However, none of the GPCs were faulty.”

The fault was a cracked diode in a multiplexer-demultiplexer, one of the units that feed the computers their data. “As a crack opened up,” the write-up explains, “it changed the diode into another type of component … a capacitor.” Some bits on the data bus shrank until some receivers could no longer see them, so the computers began receiving different sets of messages.

When a component tells different parts of a system different things, it has a Byzantine fault. The write-up’s verdict: “Given that there were four GPCs, the shuttle had sufficient redundancy to tolerate a Byzantine fault, if these FDIR algorithms had been designed correctly.” Tolerating f such faults, known as Byzantine fault tolerance (BFT), takes an expensive protocol and, where message delays have no known bound, at least 3f + 1 replicas.

Most systems should not pay for it, but every system should know which failures it is built to survive. This article covers the idea’s origins, why the bound is 3f + 1, how the classic protocol works, what it costs, and how to choose between crash and Byzantine tolerance.

From Flight Computers to Byzantine Generals

When it became clear that computers would fly commercial aircraft, Leslie Lamport recalls, NASA began funding research to make them reliable enough. One project was SIFT, a fault-tolerant computer for aircraft control at SRI International, and Lamport credits it with producing the problem and its solutions. Marshall Pease, Robert Shostak, and Lamport published them in 1980. Before that paper, Lamport writes, “it was generally assumed that a three-processor system could tolerate one faulty processor.” The paper showed that a processor that sends inconsistent information to the others can defeat any traditional three-processor algorithm.

The name came in 1982. The popularity of Dijkstra’s dining philosophers had taught Lamport that a problem told as a story gets attention. So he told one. The generals of the Byzantine army, camped around an enemy city, must agree on a battle plan and can communicate only by messenger. Some of them may be traitors. The paper’s original title was “The Albanian Generals Problem,” until Jack Goldberg suggested finding another name. The published paper reduces the problem to a commander sending an order to its lieutenants, under two conditions:

IC1. All loyal lieutenants obey the same order.

IC2. If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.

Read servers for generals and faulty nodes for traitors. IC1 is agreement: a faulty sender cannot split the honest receivers. IC2 is validity: an honest sender cannot be overruled.

The headline result covers oral messages, whose contents are entirely up to the sender. With those, the problem “is solvable if and only if more than two-thirds of the generals are loyal; so a single traitor can confound two loyal generals.” With unforgeable signed messages, it is solvable for any number of traitors. Both results assume reliable delivery, a known sender for every message, and detectable missing messages. Detection takes a timeout, which needs synchronized clocks and a known bound on message delay.

What Makes a Fault Byzantine

A fault model describes what the rest of the system sees when a component fails. A crash, or fail-stop fault, is the polite failure: the node halts and never sends anything wrong. With an omission fault, the node follows the protocol but loses some messages. A Byzantine fault is arbitrary behavior, up to showing different observers different things. A Byzantine node keeps running and can tell one peer that a value is five and another that it is nine. You cannot detect it with a heartbeat, because a traitor happily sends heartbeats.

Malice is one cause, not the definition. Miguel Castro and Barbara Liskov opened their 1999 paper on Practical Byzantine Fault Tolerance (PBFT) by naming two causes of arbitrary behavior: “malicious attacks and software errors.” Hardware does it too. The 1982 paper warned that a faulty input unit “could send a marginal signal along the wire—a signal that can be interpreted by some processors as a 0 and by others as a 1.” The shuttle’s diode did exactly that: whether a computer saw the shrunken bits depended on its receiver’s sensitivity, which varies with manufacturing, temperature, and supply voltage.

In the paper’s terms, the failing unit was a traitorous commander over four loyal lieutenants. Agreement prevents the split but cannot correct the data: “All that a Byzantine Generals solution can do,” the paper says, “is guarantee that all processors use the same input value.”

John Rushby of SRI compared bus architectures for safety-critical systems in a 2001 report. He notes that designs built for arbitrary faults are often derided for guarding against faults that never arise. His reply: such faults “certainly cannot be asserted not to occur (in fact, they have been observed in several systems that have been monitored sufficiently closely).” Arbitrary is arbitrary, whether the cause is a traitor or a particle.

Why Three Generals Cannot Outvote One Traitor

The 1982 paper argues the three-general case with two scenarios. In the first, the commander is loyal and orders an attack, but Lieutenant 2 is the traitor and tells Lieutenant 1 that the order was to retreat. IC2 requires Lieutenant 1 to attack. In the second, the commander is the traitor. It orders Lieutenant 1 to attack and Lieutenant 2 to retreat, and the loyal Lieutenant 2 truthfully reports the retreat order. Lieutenant 1 sees exactly what it saw before, so it must attack again. By the same argument, Lieutenant 2 must retreat, and the loyal lieutenants split, which breaks IC1.

The authors then warn against trusting arguments like this one. “We know of no area in computer science or mathematics in which informal reasoning is more likely to lead to errors than in the study of this type of algorithm.” The rigorous proof is in the 1980 paper. Building on it, the 1982 paper shows that no oral-message solution with fewer than 3m + 1 generals can cope with m traitors.

With four generals, one traitor can be outvoted. The paper’s algorithm for one traitor, OM(1), has three steps. The commander sends its order to every lieutenant. Each lieutenant relays the value it received to every other lieutenant. Each lieutenant then takes the majority of the values it holds, defaulting to retreat when no value has a majority. The JavaScript below implements OM(1) and tries every way one traitor can lie: as the commander, or as any lieutenant under either order. I ran it on Node.js 24.

const A = "attack";
const R = "retreat";

// The paper's majority function:
// retreat unless more than half of
// the votes say attack.
function majority(votes) {
  const yes = votes.filter(
    (v) => v === A).length;
  return yes * 2 > votes.length
    ? A : R;
}

// One run of OM(1): general 0 is
// the commander, and t is the
// traitor. A loyal commander sends
// order; the traitor sends lie(i)
// to general i.
function om1(n, t, order, lie) {
  // Step 1: the commander sends
  const got = [];
  for (let i = 1; i < n; i++) {
    got[i] = t === 0
      ? lie(i) : order;
  }
  // Steps 2 and 3: relay and vote
  const decided = [];
  for (let i = 1; i < n; i++) {
    if (i === t) continue;
    const votes = [got[i]];
    for (let j = 1; j < n; j++) {
      if (j === i) continue;
      votes.push(
        j === t ? lie(i) : got[j]);
    }
    decided.push(majority(votes));
  }
  return decided;
}

// Every way to send k orders
function allLies(k) {
  if (k === 0) return [[]];
  return allLies(k - 1).flatMap(
    (r) => [[A, ...r], [R, ...r]]);
}

const all = (xs, x) =>
  xs.every((v) => v === x);

// A lying commander: the loyal
// lieutenants must agree (IC1).
function commanderLies(n) {
  const runs = allLies(n - 1);
  return runs.map((run) => {
    const d = om1(n, 0, null,
      (i) => run[i - 1]);
    return all(d, d[0]);
  });
}

// A lying lieutenant t: the loyal
// ones must obey the order (IC2).
function lieutenantLies(n, t) {
  const to = [];
  for (let i = 1; i < n; i++) {
    if (i !== t) to.push(i);
  }
  const runs = allLies(n - 2);
  return [A, R].flatMap((order) =>
    runs.map((run) => {
      const d = om1(n, t, order,
        (i) => run[to.indexOf(i)]);
      return all(d, order);
    }));
}

function check(n) {
  const ok = commanderLies(n);
  for (let t = 1; t < n; t++) {
    ok.push(
      ...lieutenantLies(n, t));
  }
  const fails =
    ok.filter((x) => !x).length;
  return `${n} generals: ` +
    `${fails} of ${ok.length} ` +
    "runs fail";
}

console.log(check(3));
console.log(check(4));
// Prints:
// 3 generals: 2 of 12 runs fail
// 4 generals: 0 of 32 runs fail

With three generals, the two failing runs are the first scenario above, once with each lieutenant as the traitor. A loyal commander orders an attack, the traitor reports a retreat order to the other lieutenant, and the tie defaults to retreat. With four, a lying lieutenant is outvoted: each loyal lieutenant holds three values, and the traitor supplied only one. A lying commander cannot split the lieutenants either, because after the relay step they all hold the same three values. The run shows one algorithm failing with three generals; the proof shows that every algorithm must.

The algorithm also shows the cost. For m traitors, OM(m) relays each order through up to m other lieutenants, and the paper calls its solutions expensive in both time and messages.

Where 3f + 1 Comes From

Practical protocols do not relay recursively; they collect votes into quorums, sets of replicas large enough to decide. The PBFT paper explains the bound in four sentences:

This many replicas are needed because it must be possible to proceed after communicating with n − f replicas, since f replicas might be faulty and not responding. However, it is possible that the f replicas that did not respond are not faulty and, therefore, f of those that responded might be faulty. Even so, there must still be enough responses that those from non-faulty replicas outnumber those from faulty ones, i.e., n − 2f > f. Therefore n > 3f.

The same arithmetic reads more clearly as overlap. With n = 3f + 1 replicas, a quorum of n − f is 2f + 1. By inclusion–exclusion, any two quorums share at least (2f + 1) + (2f + 1) − (3f + 1) = f + 1 replicas. At most f of them are faulty, so every overlap holds an honest replica.

An honest replica never votes for two conflicting values for the same log position under the same leader. So two contradictory decisions cannot both gather a quorum under that leader: the honest replica in the overlap would have had to vote for both. That is the whole trick: make an honest node unavoidable in every quorum. For votes, one honest witness is enough. Replicated storage without signatures needs more: Dahlia Malkhi and Michael Reiter’s masking quorums overlap in at least 2f + 1 servers, so honest servers in every overlap outnumber the liars.

Crash tolerance needs fewer replicas because a crashed node never lies; it only goes quiet. Majority quorums over 2f + 1 replicas tolerate f crashes. The Raft paper calls a five-server cluster typical; it survives any two failures. But two majorities of five servers may share a single server, and a Byzantine server in that spot can vote both ways. The extra f replicas buy a guaranteed honest witness in every overlap. One Byzantine fault needs four replicas, two need seven, and three need ten, against three, five, and seven for crashes.

The function below returns, for n replicas, the largest f they tolerate and the smallest quorum q that keeps every overlap at f + 1 or more:

// For n replicas: how many faulty
// ones they tolerate (f), and the
// smallest quorum (q) such that
// any two quorums share f + 1.
function bftSizes(n) {
  const f = Math.floor(
    (n - 1) / 3);
  // Two quorums of q replicas
  // share at least 2q - n.
  const q = Math.ceil(
    (n + f + 1) / 2);
  return { n, f, q };
}

for (const n of [4, 5, 6, 7]) {
  console.log(bftSizes(n));
}
// Prints:
// { n: 4, f: 1, q: 3 }
// { n: 5, f: 1, q: 4 }
// { n: 6, f: 1, q: 4 }
// { n: 7, f: 2, q: 5 }

Five and six replicas still tolerate one fault; the extra replicas only raise the quorum. Castro and Liskov agree: replicas beyond 3f + 1 “degrade performance (since more and bigger messages are being exchanged) without providing improved resiliency.” In every row, q is at most n − f, so a quorum can still form while f replicas stay silent. Sizing in steps of three is the Byzantine version of the etcd FAQ’s advice to run an odd number of members.

Signatures, Timing, and FLP

If signatures let the loyal generals agree despite any number of traitors, why do PBFT and its successors still budget 3f + 1 replicas? The answer is timing.

In 1983, Michael Fischer, Nancy Lynch, and Michael Paterson announced the result now known as FLP. In a fully asynchronous system, where a message can take arbitrarily long, every deterministic consensus protocol can fail to terminate, even if only one process may crash. The reason is that “it is impossible for one process to tell whether another has died (stopped entirely) or is just running very slowly.” A deterministic protocol that tolerates Byzantine faults also tolerates crashes, so the result binds it too.

The authors did not call consensus hopeless. They called for weaker requirements, such as termination “with probability 1,” and for timing models closer to real systems. Both paths were taken. Michael Ben-Or published a randomized protocol in 1983. In a paper first presented in 1984, Cynthia Dwork, Nancy Lynch, and Larry Stockmeyer defined partial synchrony.

Under partial synchrony, a bound on message delay exists but is unknown, or holds only after an unknown global stabilization time. A protocol designed for that model never violates safety, meaning that correct nodes never decide differently, even while the network is fully asynchronous. Its liveness, the promise that they eventually decide, depends on the bound holding.

Dwork, Lynch, and Stockmeyer also settle the signature question. When message delays have a known bound, signatures do lower the replica count, as in the 1982 paper. When communication is only partially synchronous, Byzantine consensus needs 3f + 1 processors either way: “for partially synchronous communication, authentication does not improve resiliency.” PBFT, HotStuff, and Tendermint all assume partial synchrony, so for them 3f + 1 is not a habit but a lower bound. Signatures can still cut message costs, as HotStuff shows below, but they do not buy back a replica.

The PBFT paper shows why letting safety lean on timing is dangerous. Two earlier systems built to be practical relied on synchrony for correctness. With them, “an attacker may compromise the safety of a service by delaying non-faulty nodes or the communication between them until they are tagged as faulty and excluded from the replica group.” The authors add that such a denial-of-service attack is generally easier than taking over a node.

The design rule that follows is one I would never trade away: safety always holds, and liveness resumes once the network behaves. A system that is confidently wrong is far more dangerous than one that simply waits.

How PBFT Orders Requests

Castro and Liskov presented PBFT in February 1999, with a benchmark to match its name. In normal-case operation, a replicated NFS service ran only 3 percent slower than the standard unreplicated one. The HotStuff authors later called PBFT the first practical BFT replication solution for partial synchrony. It replicates a deterministic service across 3f + 1 replicas, which move through numbered configurations called views; in each, one replica is the primary and the others are backups. Each client request goes through three phases and a reply:

If the primary stalls or misbehaves, the backups time out and move to the next view, whose primary is the next replica in turn. The view change carries every request that may have committed into the new view, under its old sequence number. Periodic checkpoints, once certified by 2f + 1 replicas, let replicas discard old log entries.

Three caveats in the paper matter more in practice than the phases do:

What It Costs

Byzantine fault tolerance costs more on every axis:

Then there is the cost of getting the protocol right. The HotStuff paper calls the view change “the epicenter of replication” and says that view changes built on PBFT’s two voting phases are “bug-prone.” Zyzzyva shows what that means. Published in 2007, it added a speculative fast path to PBFT. Ten years later, a note whose authors include two of Zyzzyva’s designers reported: “we observe a safety violation in Zyzzyva.” The scenarios needed only four replicas and one or two view changes. The 1982 paper’s warning about informal reasoning has not aged.

HotStuff, first posted in March 2018 and published in 2019, cuts the message cost. Votes go to the leader instead of to every replica, and the leader combines n − f signed votes into one threshold signature, a quorum certificate. Once the network stabilizes, a correct leader “sends only O(n) authenticators to drive a consensus decision,” even right after replacing a failed leader. The price is one more phase per view. Its nearly uniform phases also make it easy to pipeline decisions and to rotate leaders often.

Where It Runs

Networks of parties that do not trust one another. In a public blockchain or a consortium of organizations, nobody can promise that every node is honest; tolerating dishonest nodes is the point. Tendermint, whose algorithm CometBFT implements today in the Cosmos stack, requires that “the total voting power of faulty processes is smaller than one third of the total voting power.” That is the 3f + 1 bound, weighted by voting power.

Bitcoin approaches the problem differently. Satoshi Nakamoto’s paper says the system “is secure as long as honest nodes collectively control more CPU power than any cooperating group of attacker nodes.” Proof-of-work makes a vote cost computing power rather than an IP address; it is “essentially one-CPU-one-vote.” The HotStuff authors describe Bitcoin’s core, Nakamoto consensus, as a synchronous protocol with only probabilistic safety and no finality. In 2013, Ittay Eyal and Emin Gun Sirer showed that colluding miners can earn more than their fair share without a majority. They called the 1/2 bound “wrongly assumed.”

Safety-critical hardware. In aircraft and spacecraft, the faults are usually physical rather than malicious, and a wrong value can cost lives. Honeywell’s SAFEbus, the core of the Boeing 777’s Airplane Information Management System, turns arbitrary faults into simple ones by arranging its bus interface units in self-checking pairs, doubling that hardware. In Rushby’s description, “if the members of a pair disagree, they go offline, ensuring that the effect of their failure is seen as a manifest fault (i.e., one that is easily tolerated).” Some fault modes may still “escape,” he adds, so a design must generally show complete coverage or tolerate at least one escape.

Crash or Byzantine?

Raft and Paxos are designed for crashes and lost messages, not lies. The Raft paper promises safety “under all non-Byzantine conditions.” Lamport’s “Paxos Made Simple” assumes agents that “may fail by stopping” and messages that “can be lost, but they are not corrupted.” The Tendermint paper describes where such protocols traditionally run: three to seven replicas in a data center, usually in “a single administration domain,” where Byzantine faults are considered negligible. Crash tolerance is the default there: Kubernetes, for one, keeps its API data in etcd, which uses Raft.

That default is right for most systems, and I would keep it. Byzantine fault tolerance buys protection against nodes that lie. When lying nodes are not in the threat model, the cost buys nothing. Four questions settle the choice:

The last question is easy to get wrong. On 2 November 2020, a switch in a Cloudflare data center failed partially, passing some traffic and dropping the rest, invisibly to the servers behind it. In Cloudflare’s account, one etcd member lost its link to the leader but could still reach another member. It kept calling elections, while that member kept voting for the leader it could still see. Raft elections block writes, so the cluster went read-only until the switch recovered on its own 6 minutes later.

With etcd read-only, two database clusters failed over, and a defect forced their replicas to be rebuilt. In all, Cloudflare’s API and dashboard were degraded for 6 hours and 33 minutes. The postmortem, titled “A Byzantine Failure in the Real World,” called the members’ conflicting views a Byzantine fault. A postscript corrected it: the failure “would be better characterized as an omission fault rather than a Byzantine fault. Omission faults are much more specific and can be tolerated without BFT protocols.”

In December 2020, Heidi Howard and Ittai Abraham examined link failures that leave a majority of servers connected. They showed that Raft as originally published does not guarantee liveness under such failures, and argued that Raft with two additions does. PreVote makes a candidate run a trial election before it can disrupt the cluster. CheckQuorum makes a leader that cannot hear from a majority step down. In etcd, CheckQuorum is always on, and since version 3.5, released in June 2021, PreVote is on by default too.

Inside one trust domain, arbitrary faults still happen: a corrupted disk, a bad memory module, a bug that writes garbage. The cheaper defense borrows SAFEbus’s idea and turns as many of them as it can into crashes, which crash-tolerant consensus already handles. Checksums on disk and on the wire, comparisons between replicas, and assertions that stop a process on broken state turn many wrong answers into silence. For example, etcd offers corruption checks that compare members’ stored state: on a mismatch, a starting member exits, and in a running cluster the leader raises an alarm. No such check catches every fault.

The 1982 paper’s conclusion names both the trade and its limit. The only way to reduce the cost “is to make assumptions about the type of failure that may occur,” for example that a computer “may fail to respond but will never respond incorrectly.” But “when extremely high reliability is required, such assumptions cannot be made, and the full expense of a Byzantine Generals solution is required.”

Takeaways

The Byzantine fault tolerance entry in my Software Development Principles series lists warning signs, such as a client that accepts fewer than f + 1 matching responses or tests that cover only crash failures. These are the points I would keep:

As I wrote about canonical data models, pattern correctness is not the same as pattern fit. Whether even a correct Byzantine-tolerant protocol fits depends on who or what can lie. The right tool is the cheapest one that meets the real threat model.

Further Reading