The Byzantine Generals Problem

The Byzantine Generals Problem is the abstraction Leslie Lamport, Robert Shostak, and Marshall Pease introduced in their 1982 paper of that name (Lamport, Shostak & Pease 1982) to capture the hardest kind of failure a distributed system can suffer: a component that does not merely stop, but behaves arbitrarily — sending conflicting information to different peers, lying about what it received, or actively colluding with other faulty components to defeat agreement. The paper dramatizes this as a group of generals of the Byzantine army, camped around an enemy city, who must agree on a common plan — attack or retreat — by messenger, knowing that some unknown subset of the generals (and possibly the commanding general) are traitors who will say anything to sabotage a coordinated decision. The central results are stark: with unsigned (“oral”) messages, agreement is impossible unless more than two-thirds of the participants are loyal — formally, n > 3m generals are required to tolerate m traitors, i.e. at least 3f + 1 nodes to survive f faults. If messages can be unforgeably signed, the ability of a traitor to lie is so curtailed that a solution exists for any number of traitors, with the problem becoming vacuous only below m + 2 generals. This note develops both results from the primary source, together with the earlier and more general 1980 paper they compress (Pease, Shostak & Lamport 1980) and Lamport’s own retrospective commentary on how the work came about (My Writings). One caveat governs everything below and is stated up front because it is the single most commonly dropped qualification: the entire paper lives in a synchronous model. The signed-message escape from the 3m + 1 bound is a synchronous result and does not survive the move to the partially synchronous networks real systems run on — Dwork, Lynch & Stockmeyer (1988) prove that under partial synchrony authentication buys no extra resiliency at all, and 3f + 1 returns. The problem is the theoretical foundation of the entire field of Byzantine fault tolerance (BFT), whose first practical realization was Practical Byzantine Fault Tolerance and whose modern descendants underpin permissionless blockchains.

Mental Model — Why One Liar Breaks Three Honest Nodes

The whole difficulty is contained in the smallest non-trivial case: three generals, one of them a traitor. The paper proves no solution exists here, and everything else (the 3m + 1 bound, the algorithms) is machinery to escape this trap by adding enough loyal nodes that the honest majority can always be recovered by voting.

flowchart TD
    subgraph S1["Scenario A: a loyal Lieutenant, traitor peer"]
        C1["Commander (loyal)<br/>sends 'attack' to both"]
        C1 -->|"'attack'"| L1a["Lieutenant 1 (loyal)"]
        C1 -->|"'attack'"| L2a["Lieutenant 2 (TRAITOR)"]
        L2a -.->|"lies: 'he said retreat'"| L1a
    end
    subgraph S2["Scenario B: a traitor Commander"]
        C2["Commander (TRAITOR)"]
        C2 -->|"'attack'"| L1b["Lieutenant 1 (loyal)"]
        C2 -->|"'retreat'"| L2b["Lieutenant 2 (loyal)"]
        L2b -.->|"honestly relays: 'he said retreat'"| L1b
    end

What it shows and the insight to take: Lieutenant 1 sees exactly the same thing in both scenarios — it hears 'attack' directly and 'he said retreat' from Lieutenant 2. In Scenario A the correct action is to obey the loyal commander’s 'attack'; in Scenario B, symmetry demands both loyal lieutenants reach the same decision, and since Lieutenant 2 is also loyal and heard 'retreat' directly, Lieutenant 1 must match it. A single node cannot distinguish “my peer is lying” from “the source is lying,” so no deterministic rule satisfies both cases at once. The escape is quantitative: with 3f + 1 nodes, every honest node collects enough independent testimony that a majority vote over recursively cross-checked reports always recovers the truth, no matter how the f traitors coordinate.

Historical Origin and the Name

The problem did not spring from folklore — it came out of a real fault-tolerant-computing effort. Per Lamport’s own commentary (My Writings), it “was formulated by people working on SIFT before I arrived at SRI.” SIFT (Software Implemented Fault Tolerance) was a NASA-funded project at SRI International to build an aircraft flight-control computer that stayed correct even when components failed in unpredictable ways. The formal core first appeared in the earlier paper “Reaching Agreement in the Presence of Faults” (Pease, Shostak & Lamport, Journal of the ACM 27(2), April 1980), which already established the 3f + 1 oral-message bound and the signed-message improvement; the 1982 TOPLAS paper is the famous, more accessible retelling built around the generals allegory.

The colorful name is itself a small piece of computing history, and the version usually retold is wrong. Inside the impossibility proof the authors reduce a general solution to the three-general case by having each general simulate several others; to keep the two levels of the argument distinct, the simulated generals of the assumed-but-impossible solution are called Albanian and the real ones Byzantine — preserved verbatim in the paper (“we call the generals of the assumed solution Albanian generals, and those of the constructed solution Byzantine generals”). That reads like a deliberate two-level naming device. Lamport’s own annotation says it is a fossil of the paper’s original title:

“I wanted to assign the generals a nationality that would not offend any readers. At the time, Albania was a completely closed society, and I felt it unlikely that there would be any Albanians around to object, so the original title of this paper was The Albanian Generals Problem. Jack Goldberg was smart enough to realize that there were Albanians in the world outside Albania, and Albania might not always be a black hole, so he suggested that I find another name. The obviously more appropriate Byzantine generals then occurred to me.” — Lamport, My Writings

So the choice was not “a defunct empire, to avoid impugning a living nation”: it was first a living but hermetically sealed nation, and only after a colleague’s objection a defunct empire. Lamport is explicit that the whole point of the 1982 paper was the rename — “The main reason for writing this paper was to assign the new name to the problem. But a new paper needed new results as well.” He credits the story-telling instinct to Dijkstra: the dining philosophers problem, he says, “received much more attention than it deserves” purely because it was posed as a story, and “the best way to attract attention to a problem is to present it in terms of a story.”

The same annotation is candid about authorship, which matters because the note’s two algorithms have different authors: “The 4-processor solution presented in this paper and the general impossibility result were obtained by Shostak; Pease invented the 3n + 1-processor solution. My contribution to the work in this paper was the solution using digital signatures.” Lamport also disclaims the credit he usually receives — “I am often unfairly credited with inventing the Byzantine agreement problem” — and the term Byzantine itself only appeared with the 1982 paper, not with the 1980 one that proved the results.

The Formal Problem: Interactive Consistency

Strip away the allegory. A commanding general must send an order value to n − 1 lieutenant generals. Each general is either loyal (executes the protocol faithfully) or a traitor (behaves arbitrarily). The goal is not to force the traitors to do anything — they are unconstrained — but to protect the loyal generals. A solution must guarantee two interactive consistency conditions:

• IC1. All loyal lieutenants obey the same order. (Agreement.)
• IC2. If the commanding general is loyal, then every loyal lieutenant obeys the order the commander sends. (Validity — the loyal decision cannot be hijacked when the source is honest.)

Note the asymmetry that makes IC2 necessary: IC1 alone is satisfiable trivially (everyone always attacks, ignoring all messages), so IC2 rules out that degenerate “agreement” by demanding the outcome track a loyal commander’s actual intent. When the commander is a traitor, IC1 still forces the loyal lieutenants to converge on some common value — it need not be a value the commander “wanted,” only a value they all share.

A traitorous commander may refuse to send any order at all. Because the lieutenants must decide something, the protocol fixes a default order — the paper uses RETREAT — that a loyal general adopts when it receives no value. This “absence maps to a fixed default” trick recurs throughout: it denies a traitor the ability to force different loyal generals into different states merely by staying silent toward some of them.

The Impossibility: No Solution for n ≤ 3m

The Mental Model diagram is the proof for n = 3, m = 1. The paper first argues it informally via the two indistinguishable scenarios, then — with a characteristic Lamport warning that “informal reasoning … is more likely to lead to errors than in the study of this type of algorithm” — refers to the rigorous proof in the 1980 predecessor.

The general bound follows by a simulation (reduction) argument. Suppose, for contradiction, a protocol existed that let 3m or fewer generals tolerate m traitors. Take three “Byzantine” generals and have each one simulate roughly one-third of the 3m “Albanian” generals. The paper’s split is exact and worth quoting because it is routinely garbled: “The Byzantine commander simulates the Albanian commander plus at most m − 1 Albanian lieutenants, and each of the two Byzantine lieutenants simulates at most m Albanian lieutenants.” Each of the three therefore stands in for at most m Albanians. A single Byzantine traitor then corresponds to at most m Albanian traitors, so the assumed solution’s guarantees (IC1, IC2 for the Albanians) carry down: by IC1 all the Albanian lieutenants simulated by one loyal Byzantine lieutenant obey the same order, which is therefore the order that Byzantine lieutenant obeys. The result is a three-general solution tolerating one traitor — which we already know is impossible. Contradiction. Hence:

Theorem (Impossibility). There is no solution to the Byzantine Generals Problem, using oral messages, for n < 3m + 1 generals in the presence of m traitors.

Equivalently, tolerating f arbitrary faults requires n ≥ 3f + 1 nodes. The intuition behind the “two-thirds” threshold reappears cleanly in Practical Byzantine Fault Tolerance: an honest node must be able to reach a decision after hearing from n − f nodes (the f faulty ones may never reply); of those n − f responses, up to f could themselves be from traitors; so the honest responses n − 2f must strictly outnumber the traitorous f, giving n − 2f > f, i.e. n > 3f.

The authors also puncture a natural hope: maybe the difficulty is the demand for exact agreement? They show approximate agreement is just as hard — if the generals need only agree on an attack time within 10 minutes of one another (conditions IC1′/IC2′), the problem is still unsolvable unless more than two-thirds are loyal. The reduction is concrete and pleasingly cheap: the commander encodes “attack” as an attack time of 1:00 and “retreat” as 2:00, and each lieutenant decides attack if the time it obtains is 1:10 or earlier, retreat if 1:50 or later, and otherwise asks the other lieutenant what it decided and copies that (defaulting to retreat if the other also deferred). IC2′ makes a loyal commander’s intent survive the encoding, and IC1′ guarantees the two loyal lieutenants’ times cannot straddle the 1:10/1:50 gap in opposite directions — so a hypothetical approximate-agreement protocol would yield an exact-agreement protocol for three generals, which is impossible. The obstacle is Byzantine lying itself, not the precision of the target.

The 1980 Predecessor — Interactive Consistency, Rigorously

The 1982 paper’s informal three-general argument comes with an unusual authorial warning — “we strongly advise the reader to be very suspicious of such nonrigorous reasoning… We know of no area in computer science or mathematics in which informal reasoning is more likely to lead to errors” — and then defers the actual proof to reference [3]: “Reaching Agreement in the Presence of Faults”, Journal of the ACM 27(2), April 1980 (Pease, Shostak & Lamport 1980; received November 1978, accepted May 1979). Because the 1982 retelling is the one everyone reads, the 1980 results are widely mis-summarized. Three differences matter.

It solves a strictly more general problem. The 1982 formulation is one commander broadcasting one order. The 1980 formulation is interactive consistency: every one of n processors holds a private value v_p (a clock reading, a sensor sample), and every nonfaulty processor must compute the same whole vector of n values, with the entry for each nonfaulty processor equal to that processor’s actual private value. Entries for faulty processors may be arbitrary — “it matters only that the nonfaulty processors compute exactly the same value for any given faulty processor.” Once every nonfaulty processor holds the same interactive-consistency (i.c.) vector, they can each apply any averaging or filtering function to it and necessarily land on the same answer. The 1982 broadcast problem is what you get by running one instance per source: “the ith general sends his value of v(i) by using a solution to the Byzantine Generals Problem to send the order ‘use v(i) as my value’.”

The impossibility proof is much stronger than the picture-based argument. The 1980 proof does not reason about a single scenario; it partitions the processor set P into three nonempty groups A, B, C, each of size at most m (possible exactly when n ≤ 3m), and constructs three scenarios α, β, σ that are respectively consistent with A ∪ C, B ∪ C and A ∪ B being the nonfaulty set, such that no processor in A can distinguish α from σ and no processor in B can distinguish β from σ. In σ the members of A must therefore record v for members of C while the members of B record v′ ≠ v, contradicting interactive consistency. Critically, the theorem is stated over scenarios defined on all nonempty strings over P, so it rules out solutions “even allowing an infinite number of rounds of exchange” — no amount of extra messaging rescues n ≤ 3m.

The signature result is stated differently, and more weakly than people remember. The 1980 paper does not use the word signature; it uses authenticators. An authenticator is “a redundant augment to a data item that can be created, ideally, only by the originator,” and the assumption it buys is precisely that “a faulty processor may ‘lie’ about its own value and may refuse to relay values it has received, but may not relay altered values without betraying itself as faulty.” Under that assumption the paper gives a procedure — collect the set S_pq of all non-NIL values σ_p(pwq) over authenticator chains w of distinct processors of length ≤ m, record the unique element if there is exactly one, NIL otherwise — and proves it “guarantees interactive consistency for any n ≥ m.”

Uncertain

Verify: the exact bound the authenticated/signed algorithm achieves. Reason: two primary sources phrase it differently. The 1980 paper’s own text and abstract say interactive consistency is achievable “for arbitrary n ≥ m ≥ 0” with authenticators, and the 1982 paper says SM(m) works for any number of traitors (vacuous below m + 2 generals); but Lamport’s retrospective annotation on the same 1980 paper says “if digital signatures are used, 2n + 1 processors are enough” (his n = number of faults, i.e. 2f + 1). The most likely reconciliation is that these measure different things — n ≥ m suffices to make the i.c. vector itself consistent, while 2f + 1 is what you need for the filtering function applied to that vector (a majority or median) to still be dominated by nonfaulty entries — but this reconciliation is my reading, not a statement either source makes. To resolve: read Lamport’s [29] (“The Implementation of Reliable Distributed Multiprocess Systems”) on which he says his signature contribution was based. uncertain

Round complexity: m + 1, and that is tight. The 1980 algorithm uses m + 1 rounds of information exchange (the m = 1, n = 4 case is two rounds: exchange private values, then exchange the results of the first exchange). The 1982 conclusion notes that OM(m) and SM(m) “both require message paths of length up to m + 1” and that “Fischer and Lynch have shown that this must be true for any solution that can cope with m traitors, so our solutions are optimal in that respect.” That lower bound is its own paper: “A Lower Bound for the Time to Assure Interactive Consistency” (Fischer & Lynch, Information Processing Letters 14(4), 13 June 1982), which shows “any algorithm which assures interactive consistency in the presence of m faulty processors requires at least m + 1 rounds of communication.” Two independent optimality results therefore pin the shape of the problem: 3m + 1 nodes (Pease–Shostak–Lamport) and m + 1 rounds (Fischer–Lynch).

Finally, the 1980 conclusion is the clearest statement anywhere of why the field exists at all, and it is an admission of error: in SIFT, “in the preliminary stages of the design of this system, it was naively assumed that simple majority voting schemes could be devised to treat these situations. The gradual realization that simple majorities are insufficient led to the results reported here.” The three named applications were clock synchronization, stabilization of sensor input, and agreement on the results of diagnostic tests.

timeline
    title Lineage of the Byzantine agreement results, as dated by the papers themselves
    1978 : SIFT design at SRI assumes simple majority voting suffices : Reaching Agreement submitted (Nov 1978)
    1980 : JACM 27(2) — interactive consistency, 3m+1 tight, authenticators for n >= m
    1982 : TOPLAS 4(3) — the Byzantine retelling, OM(m), SM(m), missing paths : IPL 14(4) — Fischer and Lynch, m+1 rounds is a lower bound
    1983 : JACM 30(3) — Lamport, The Weak Byzantine Generals Problem
    1985 : JACM 32(2) — Fischer, Lynch and Paterson, FLP impossibility (asynchrony, one crash)
    1988 : JACM 35(2) — Dwork, Lynch and Stockmeyer, partial synchrony; authentication stops helping
    1999 : OSDI — Castro and Liskov, PBFT; 3f+1 made practical

What it shows and the insight to take: the famous 1982 paper sits in the middle of the story, not at its start. The mathematics was done in 1980; the 1982 paper’s own author says its main purpose was the rename. And the two impossibility results everyone cites together — 3m + 1 and FLP — are separated by five years and describe different obstacles (see the section below).

Solution I — Oral Messages: the OM(m) Algorithm

An oral message is one whose content is entirely under the sender’s control. The model is fixed by three assumptions:

• A1. Every message that is sent is delivered correctly. (No message loss.)
• A2. The receiver of a message knows who sent it. (Authenticated channels — a traitor cannot impersonate.)
• A3. The absence of a message can be detected. (Enables the RETREAT default via timeout.)

A1 and A2 prevent a traitor from interfering with messages exchanged between two other generals; A3 foils a traitor who tries to block a decision by staying silent. Under these, the paper gives the recursive Oral Message algorithm OM(m), which solves the problem for n ≥ 3m + 1. It relies on a majority function: majority(v₁, …, vₙ₋₁) returns the majority value if one exists, else RETREAT (the median is an alternative when values are ordered).

Algorithm OM(0):
  (1) The commander sends his value to every lieutenant.
  (2) Each lieutenant uses the value he receives (or RETREAT if none).
 
Algorithm OM(m), m > 0:
  (1) The commander sends his value to every lieutenant.
  (2) For each i, let v_i be the value Lieutenant i received from the commander
      (or RETREAT). Lieutenant i then acts as the commander in OM(m−1) to send
      v_i to each of the n−2 OTHER lieutenants.
  (3) For each i and each j ≠ i, let v_j be the value Lieutenant i received from
      Lieutenant j in step (2) via OM(m−1) (or RETREAT). Lieutenant i uses
      majority(v_1, …, v_{n−1}).

Read the recursion as “trust no single relay; cross-check every report through everyone else.” In step (2) each lieutenant re-broadcasts what it heard, but not directly — it recursively invokes OM(m − 1), so that re-broadcast is itself cross-checked one level deeper. The recursion bottoms out at OM(0), plain relaying. Each additional tolerated fault adds one level: OM(m) invokes n − 1 separate executions of OM(m − 1), each of which invokes n − 2 executions of OM(m − 2), and so on, so OM(m − k) is called (n − 1)(n − 2) ⋯ (n − k) times. The paper’s own accounting of the total is precise: OM(m) and SM(m) “involve sending up to (n − 1)(n − 2) ⋯ (n − m − 1) messages” — m + 1 descending factors, not m. For the smallest interesting case m = 1, n = 4 that is 3 × 2 = 6 relayed messages on top of the commander’s 3; for m = 2, n = 7 it is 6 × 5 × 4 = 120. This factorial blow-up, and not the 3m + 1 replica count, is the reason the results were considered impractical for two decades.

Because the same lieutenant sends many distinct messages to the same peer as the recursion unfolds, they must be distinguishable: “all ambiguity is removed if each lieutenant i prefixes the number i to the value v_i that he sends in step (2).” A value arriving at depth k therefore carries a k-long chain of lieutenant numbers — the oral-message ancestor of the signature chains in SM(m) below, except that a traitor can fabricate the chain freely.

The worked case m = 1, n = 4 (one traitor). Suppose Lieutenant 3 is the traitor and the commander is loyal, sending value v to all three lieutenants. Lieutenant 2, in step (3), computes over three values: v₁ = v (relayed honestly by Lieutenant 1 via OM(0)), v₂ = v (its own copy from the commander), and v₃ = x (garbage relayed by the traitor Lieutenant 3). It takes majority(v, v, x) = v — the correct value. Now flip it: the commander is the traitor and sends arbitrary x, y, z to the three loyal lieutenants. Each honest lieutenant relays what it got, so all three compute majority(x, y, z) over the same multiset and obtain the same result — whatever it is — satisfying IC1. In neither case can the single traitor split the loyal lieutenants.

flowchart LR
    subgraph R1["Round 1 — OM(1) step (1): commander broadcasts"]
        C["Commander (loyal)<br/>value v"]
        C -->|v| L1["L1 (loyal)"]
        C -->|v| L2["L2 (loyal)"]
        C -->|v| L3["L3 — TRAITOR"]
    end
    subgraph R2["Round 2 — OM(0): each lieutenant relays what it heard"]
        L1 -->|"v (honest)"| L2b["L2 collects"]
        L3 -->|"x (lie)"| L2b
        L2 -->|"own copy v"| L2b
    end
    L2b --> M["majority(v, v, x) = v<br/>IC2 satisfied"]

What it shows and the insight to take: the traitor L3 gets exactly one vote in L2’s tally, because L2 also holds its own direct copy from the commander and one honest relay from L1. With n ≥ 3m + 1 there are always strictly more honest relays than traitorous ones at every level of the recursion, so majority cannot be flipped. The mirror case — a traitorous commander sending arbitrary x, y, z — works for the opposite reason: all three lieutenants are loyal, all three relay honestly, so all three compute majority(x, y, z) over the same multiset and agree on whatever it yields, satisfying IC1 without anyone learning the “right” answer, because there is none.

The correctness is captured by:

Lemma 1. For any m and k, OM(m) satisfies IC2 if there are more than 2k + m generals and at most k traitors.

Theorem 1. For any m, OM(m) satisfies IC1 and IC2 if there are more than 3m generals and at most m traitors.

The proofs are inductions on m: Lemma 1’s key step observes that with n > 2k + m there are n − 1 > 2k + (m − 1) ≥ 2k lieutenants, so a majority of the recursively-obtained values are correct; Theorem 1 then handles the traitorous-commander case by noting there are then at most m − 1 traitorous lieutenants among more than 3m − 1, letting the induction hypothesis carry.

Solution II — Signed Messages: the SM(m) Algorithm

The Mental Model showed that a traitor’s power comes from its ability to say different things to different peers and have those lies be indistinguishable from honest relays. Unforgeable signatures destroy exactly that power. The oral assumptions A1–A3 are augmented with:

• A4. (a) A loyal general’s signature cannot be forged, and any alteration of the contents of his signed messages can be detected. (b) Anyone can verify the authenticity of a general’s signature.

Note the asymmetry inside A4, which the note-taking literature routinely flattens: part (a) is scoped to a loyal general’s signature, but part (b) is scoped to any general’s signature — verification is universal, unforgeability is not. Crucially, no assumption is made about a traitor’s signature — traitors may forge each other’s signatures and collude freely. With A4 in place, a lieutenant can no longer misreport what the commander said, because the commander’s order carries the commander’s own signature, and any tampering is detectable. This collapses the requirement dramatically:

Theorem 2. For any m, algorithm SM(m) solves the Byzantine Generals Problem if there are at most m traitors.

The only structural constraint left is n ≥ m + 2 (with fewer than m + 2 generals the problem is vacuous). The SM(m) algorithm has each lieutenant maintain a set Vᵢ of properly-signed orders it has seen:

Algorithm SM(m):   (General 0 is the commander; notation "v:i" = value v signed by General i)
  Initially V_i = ∅.
  (1) The commander signs and sends his value to every lieutenant.
  (2) For each lieutenant i:
      (A) If i receives "v:0" from the commander and V_i is still empty,
          he sets V_i := {v} and sends "v:0:i" to every other lieutenant.
      (B) If i receives "v:0:j1:…:jk" and v ∉ V_i,
          he adds v to V_i, and if k < m, appends his signature and forwards
          "v:0:j1:…:jk:i" to every lieutenant not already in {j1,…,jk}.
  (3) When lieutenant i will receive no more messages, he obeys choice(V_i).

Here choice(V) maps the accumulated set of orders to a single decision — for example choice({v}) = v, choice(∅) = RETREAT, and the median for larger sets. The whole scheme is certificate accumulation: a signed order chained through k distinct lieutenant signatures is proof that those k generals all endorsed it, and a traitor cannot manufacture such a chain for a value the loyal commander never signed. The three-general case that was impossible with oral messages now works: if a traitorous commander sends "attack" to Lieutenant 1 and "retreat" to Lieutenant 2, both loyal lieutenants exchange their signed orders, both end up with V₁ = V₂ = {"attack","retreat"}, and both apply the same choice — reaching agreement and, as the paper stresses, learning who the traitor is: “unlike the situation in Figure 2, the lieutenants know the commander is a traitor because his signature appears on two different orders, and A4 states that only he could have generated those signatures.” Accountability is a free by-product of signatures that oral messages cannot provide.

Three implementation details of SM(m) are worth carrying because they are almost never reproduced:

• Termination is decidable, not just timeout-based. Step (3) says “when Lieutenant i will receive no more messages” — and the paper shows this is well-defined: for each signature sequence j₁, …, j_k with k ≤ m a lieutenant can receive at most one message of the form v:0:j₁:…:j_k, so if each j_k is required either to send such a message or to send an explicit “I will not send one,” a lieutenant can tell exactly when it is done. Timeout (assumption A3) is the fallback, not the primary mechanism.
• The last signature is dead weight. “If he is the mth lieutenant to add his signature to the order, then that signature is not relayed to anyone else by its recipient, so it is superfluous.” Consequence: in SM(1) the lieutenants need not sign at all — assumption A2 (the receiver knows who sent a message) already does the work.
• Message packets have a checkable cardinality. If a lieutenant physically copies a message rather than re-generating it, a well-formed packet signed by k lieutenants must contain exactly (n − k − 2)(n − k − 3) ⋯ (n − m − 2) identical copies; anything else is discarded. This is a structural integrity check independent of the cryptography.

Lamport’s annotation adds a sting that survives to today’s protocol design. The signatures in SM(m), he writes, “are a metaphor. Since the signatures need be secure only against random failure, not against an intelligent adversary, they are much easier to implement than true digital signatures. However, this point seems to have escaped most people, so they rule out the algorithms that use digital signatures because true digital signature algorithms are expensive. Thus, 3n + 1-processor solutions are used even though there are satisfactory 2n + 1-processor solutions.” The paper itself backs this up with a concrete cheap construction for the random-malfunction case: encode messages as positive integers less than a power of two P, let S_i(M) = M · K_i mod P for a randomly chosen odd K_i < P, and verify with the modular inverse K_i⁻¹. A processor that does not hold K_i forges a signature with probability 1/P. Only when the fault is a malicious intelligence — “a perfectly good processor being operated by a human who is trying to disrupt the system” — does the construction become a genuine cryptography problem, for which the paper points at Diffie–Hellman and RSA. One operational caveat comes with it: because a seen signature is trivially replayable, “it is important that the same message never have to be signed twice… sequence numbers should be appended to the values to guarantee uniqueness.”

Missing Communication Paths — Where Signatures Win Twice

The algorithms above assume every general can message every other directly. Section 5 of the paper relaxes this by modelling the generals as nodes of a simple, finite, undirected graph G in which an arc means “can send directly.” The two algorithms then diverge sharply, and this is the second and less-known place where signatures buy something real.

The paper’s connectivity notion is exact rather than hand-wavy. A set of nodes {i₁, …, i_p} is a regular set of neighbors of node i when (i) each i_j is a neighbor of i, and (ii) for every general k ≠ i there exist paths γ_{j,k} from i_j to k that avoid i and that are pairwise node-disjoint except at k itself. A graph is p-regular if every node has such a set of p distinct neighbors. The oral algorithm generalizes to OM(m, p): the commander picks a regular neighbor set N of size p, sends to N, and each i ∈ N forwards to every other node either along the disjoint paths γ_{i,k} (when m = 1) or by recursively running OM(m − 1, p − 1) on the graph with the original commander deleted — which is legal precisely because deleting one node from a p-regular graph leaves a (p − 1)-regular graph. Theorem 3 then gives: OM(m, p) solves the problem for any p ≥ 3m and at most m traitors.

This is a strong hypothesis, and the paper says so. A 3m-regular graph necessarily has at least 3m + 1 nodes, so at the minimum node count 3m-regularity is complete connectivity and OM(m, 3m) collapses back into plain OM(m). A footnote concedes that “a recent algorithm of Dolev [2] requires less connectivity.”

SM(m) behaves completely differently, and this half of Section 5 is almost always dropped from summaries. Signed orders can simply be relayed hop by hop, so the requirement collapses to the weakest possible one — that the subgraph induced by the loyal generals be connected:

Theorem 4. For any m and d, if there are at most m traitors and the subgraph of loyal generals has diameter d, then SM(m + d − 1) (with the commander sending only to neighbours, and each lieutenant forwarding only to neighbours not already in the signature chain) solves the Byzantine Generals Problem.

Corollary. If the graph of loyal generals is connected, then SM(n − 2) solves the problem for n generals — regardless of the number of traitors.

The corollary follows by counting: a connected graph’s diameter is smaller than its node count, so more than d generals are loyal and fewer than n − d are traitors; set m = n − d − 1. And even when the loyal subgraph is not connected, the paper shows SM(m + d − 1) still guarantees two useful partial properties: any two loyal generals joined by an all-loyal path of length ≤ d obey the same order, and a loyal lieutenant joined to a loyal commander by an all-loyal path of length ≤ m + d obeys his order. Byzantine agreement degrades gracefully by connected component rather than failing globally.

Aspect	OM(m) — oral	SM(m) — signed
Node bound (complete graph)	n ≥ 3m + 1, and tight	any n; vacuous below m + 2
Connectivity needed	G must be 3m-regular	loyal subgraph connected; use SM(m + d − 1), d = its diameter
Rounds / path length	up to m + 1, optimal per Fischer–Lynch	up to m + 1; up to m + d on sparse graphs
Messages	up to (n−1)(n−2)⋯(n−m−1)	same order; last signature superfluous
Communication-link failure	indistinguishable from node failure — eats into the m budget	insensitive: a dead link merely lowers graph connectivity
Detects the traitor?	no	yes, when two conflicting orders carry the same signature
Survives partial synchrony?	bound stays 3f + 1	no advantage — bound returns to 3f + 1 (DLS 1988)

What it shows and the insight to take: every row favours signatures except the last, and the last is the one that decides what real systems do. Under the synchronous model of the 1982 paper, signed messages dominate on node count, connectivity, and diagnosability. Under the partially synchronous model of the Internet, that entire advantage evaporates and both columns collapse to 3f + 1 — which is why Practical Byzantine Fault Tolerance pays for 3f + 1 replicas and uses cryptography, rather than treating the cryptography as a way to shrink the replica group.

Implementing A1–A4 — the Assumptions Are Not Free

Section 6 of the paper — the part that gets skipped — walks each assumption back to hardware and is the most engineering-relevant material in it. Every assumption costs something, and one of them is circular.

A1 (reliable delivery) silently taxes your fault budget. “For the oral message algorithms OM(m) and OM(m, p), the failure of the communication line joining two processors is indistinguishable from the failure of one of the processors. Hence, we can only guarantee that these algorithms will work in the presence of up to m failures, be they processor or communication line failures.” A shop that sizes m against expected node failures and then loses a link has already overrun its budget. SM(m), by contrast, “is insensitive to communication line failure” as long as a failed line cannot forge a signed message — a dead link just removes an edge from the graph, which Theorem 4 already tolerates.

A2 (sender identification) means physical wires, or signatures. “In practice, this means that interprocess communication be over fixed lines rather than through some message switching network. (If a switching network is used, then faulty network nodes must be considered, and the Byzantine Generals Problem appears again.)” The recursion here is the point: putting a router in the middle does not remove the problem, it reproduces it one layer down. A2 becomes unnecessary if A4 holds and everything is signed, since impersonation would then require forgery.

A3 (detecting a missing message) drags in clock synchronization, which is exactly as hard as the original problem. Detecting absence means timing out, and timing out needs two things: a fixed maximum message generation-and-transmission time μ, and clocks synchronized to within some maximum skew τ. Then any message a nonfaulty processor should begin generating by time T on its clock arrives by T + μ + τ on the receiver’s, and in SM(m) a processor waits until T₀ + k(μ + τ) for a message bearing k signatures. But clocks drift, so they must be resynchronized — “and this is as difficult a problem as the Byzantine Generals Problem itself.” The paper is not hand-waving here; it states a genuine impossibility for the class of algorithms whose only triggers are a fixed initial time, message receipt, and a randomly chosen timer value: “no such algorithm can solve the Byzantine Generals Problem if messages can be transmitted arbitrarily quickly, even if there is an upper bound on message transmission delay. Moreover, no solution is possible even if we restrict the traitors so that the only incorrect behavior they are permitted is the failure to send a message.” Only putting a lower bound on delay as well lets processors build clocks by exchanging messages. This is the ancestor of the timing assumptions in failure detectors and of the GST machinery discussed below.

A validity bonus you get for free with medians. If majority and choice are taken to be median functions rather than plurality-vote functions, the algorithms acquire a range property: “the value obtained by the nonfaulty processors lies within the range of values provided by the input unit.” That is what makes the results usable for the sensor-stabilization and clock-synchronization applications that motivated SIFT, where the values are real numbers and no two honest readings are ever bit-identical. The paper is explicit that the pathological input is not always a malicious one — “different processors can get different values even from a nonfaulty input unit if they read the value while it is changing.”

The hardware temptation, and why it fails. “It is tempting to try to circumvent the problem with a ‘hardware’ solution. For example, one might try to insure that all processors obtain the same input value by having them all read it from the same wire. However, 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.” This is metastability, and it means the Byzantine problem is not an artifact of software layering: a single shared wire is itself a Byzantine source.

Three Impossibility Results That Are Not the Same Thing

These are conflated constantly — including in interview answers, where “you can’t do consensus with Byzantine faults” is used as a catch-all. They have different fault models, different timing models, and different conclusions.

flowchart TB
    A["Pease, Shostak and Lamport 1980 / 1982<br/><b>3m+1 bound</b>"] --> A1["Model: SYNCHRONOUS<br/>Fault: Byzantine (arbitrary)<br/>Says: no protocol exists at all<br/>when n is at most 3m, at any round count<br/>Escape: signatures (n at least m)"]
    B["Fischer, Lynch and Paterson 1985<br/><b>FLP impossibility</b>"] --> B1["Model: fully ASYNCHRONOUS<br/>Fault: ONE crash (process stops)<br/>Says: no deterministic protocol is<br/>partially correct AND always terminates<br/>Escape: randomization, partial synchrony,<br/>failure detectors"]
    C["Dwork, Lynch and Stockmeyer 1988<br/><b>partial synchrony</b>"] --> C1["Model: bounds exist but unknown,<br/>or hold only after GST<br/>Fault: all four classes<br/>Says: consensus IS solvable, and<br/>authentication does NOT lower<br/>the Byzantine bound below 3t+1"]
    A1 --> D["What PBFT actually assumes"]
    B1 --> D
    C1 --> D

What it shows and the insight to take: the 3m + 1 bound is about how many liars a vote can absorb; FLP is about whether you can ever be sure you are finished. They are orthogonal, which is why FLP’s fault model is a single crash — a process that “takes infinitely many steps” is nonfaulty, one that stops is faulty (Fischer, Lynch & Paterson 1985). FLP’s Theorem 1 is the terse “No consensus protocol is totally correct in spite of one fault,” where totally correct in spite of one fault means partially correct (no two decision values; both values reachable) and every admissible run is a deciding run. Byzantine behaviour is not required, and neither is a large n. Conversely the 3m + 1 bound holds in a fully synchronous system where FLP has nothing to say.

The third result is the one that governs everything built after 1988 and is the least quoted of the three. Dwork, Lynch & Stockmeyer (1988) define partial synchrony in two flavours — bounds Δ (message delay) and Φ (relative processor speed) exist but are unknown a priori; or they are known but hold only from an unknown Global Stabilization Time (GST) onward — and prove the two are, for consensus purposes, the same condition, because “safety violations must occur at some finite point in time, and there would be some continuation of the violating execution in which Δ eventually holds.” That equivalence is the modern safety/liveness split: safety must hold under full asynchrony, termination is required only once the network behaves. Their Table I gives the resiliency for each fault class:

Failure type	Synchronous	Asynchronous	Partially synchronous communication
Fail-stop	t	∞ (impossible)	2t + 1
Omission	t	∞	2t + 1
Authenticated Byzantine	t	∞	3t + 1
Byzantine	3t + 1	∞	3t + 1

(N_min is the smallest number of processors admitting a t-resilient protocol; ∞ means no protocol exists for any N.)

What it shows and the insight to take: read the Authenticated Byzantine row across. Under synchrony, authentication is worth everything — N_min drops from 3t + 1 all the way to t, which is exactly SM(m)’s result. Under partial synchrony it is worth nothing: 3t + 1 either way. The paper says so in one sentence — “for partially synchronous communication, authentication does not improve resiliency.” So the popular summary “signatures make the two-thirds bound go away” is true only inside the 1982 paper’s synchronous world. Castro’s own thesis restates the same pair of facts when justifying PBFT’s design: “in a synchronous system, it is possible to solve the Byzantine consensus problem with any number of faulty participants when using signatures [PSL80]. However, it is necessary to have fewer than one third faulty participants to solve this problem with symmetric authentication” (Castro 2001, §3.1).

Why It Matters — from Impossibility to Practice

For nearly two decades the Byzantine Generals results were regarded as important but impractical: OM(m)’s factorial message fan-out and the reliance on synchronous rounds made real deployment prohibitive. The paper’s own conclusion is resigned about it — “Achieving reliability in the face of arbitrary malfunctioning is a difficult problem, and its solution seems to be inherently expensive. The only way to reduce the cost is to make assumptions about the type of failure that may occur.” The problem’s true significance is as a boundary condition. It defines the price of surviving arbitrary faults — 3f + 1 replicas and, in practice, O(n²) communication — that every subsequent protocol negotiates against. The breakthrough was Practical Byzantine Fault Tolerance (Castro & Liskov, 1999), which kept the 3f + 1 bound but reorganized the message pattern into a fixed three-phase protocol efficient enough to run a real file system, and which weakened the timing model from full synchrony to the partial synchrony of Dwork–Lynch–Stockmeyer, sidestepping the FLP Impossibility Result for liveness while never trading away safety. From there the lineage runs to Tendermint/CometBFT, HotStuff, and the BFT engines of permissionless blockchains, where “traitors” are no longer a metaphor but the assumed behavior of adversarial, self-interested participants — a shift that changes the analysis enough to deserve its own treatment, in Consensus as a Coordination Game (see also Major System Designs MOC for blockchain case studies).

A closing historical note from Lamport’s annotation, on whether any of this ever reached the aircraft it was designed for: “Over the years, I often wondered whether the people who actually build airplanes know about the problem of Byzantine failures. In 1997, I received email from John Morgan who used to work at Boeing. He told me that he came across our work in 1986 and that, as a result, the people who build the passenger planes at Boeing are aware of the problem and design their systems accordingly.”

Weakened Variants — Buying the Bound Down

If 3m + 1 is too expensive, the honest question is what you can give up. The paper and its immediate successors map three doors, and two of them are locked.

Give up exact agreement? Already ruled out above: IC1′/IC2′ approximate agreement is exactly as hard, by an explicit reduction.

Give up correctness of the agreed value when a fault occurs? This is the Weak Byzantine Generals Problem, defined by Lamport in JACM 30(3), 1983 (Lamport 1983). It “is weakened by allowing them to agree upon an ‘incorrect’ value if a failure occurs” — which is exactly what a distributed-transaction commit protocol wants, since aborting on any hint of trouble is a legitimate outcome (see Two-Phase Commit). The abstract’s verdict: “like the original Byzantine Generals Problem, the weak version can be solved only if fewer than one-third of the processes may fail. Unlike the original problem, an approximate solution exists that can tolerate arbitrarily many failures.” So weakening the validity requirement does not move the exact-agreement bound at all; only weakening agreement itself does.

Give up on liars, and assume only crashes? This is the door everyone actually walks through, and it is why Paxos High-Level and Raft exist. The cost drops from 3f + 1 to 2f + 1 and from factorial fan-out to a leader broadcast. The engineering judgment is entirely about whether a compromised or buggy node in your deployment can emit inconsistent data to different peers, not merely stop.

It is worth situating Byzantine faults in the broader failure taxonomy (see Failure Models in Distributed Systems). Most production infrastructure assumes only crash-stop or crash-recovery faults — nodes that halt but never lie — and protocols like Paxos High-Level and Raft tolerate f such faults with only 2f + 1 nodes (a bare majority), a much cheaper bar than 3f + 1. Byzantine tolerance is reserved for settings where a component may be compromised or adversarial: multi-organization systems, aerospace/defense (SIFT’s original domain), and trustless distributed ledgers. Choosing 3f + 1 BFT where crash tolerance would do is a common over-engineering mistake; conversely, assuming crash-only faults in an adversarial setting is a security hole.

Common Misunderstandings

• “3f + 1 means it tolerates one-third faulty nodes.” Precisely: it tolerates f where n ≥ 3f + 1, i.e. strictly fewer than one-third of the nodes may be Byzantine. With exactly 3f nodes, f faults break agreement.
• “Signatures make Byzantine agreement free.” In the synchronous model of the paper they lower the node bound dramatically and simplify the argument, but they add cryptographic cost, a key-distribution assumption (A4), and do not by themselves solve the timing problem. Signatures curb lying about message content, not withholding or delaying messages. And the node-count win is model-dependent: under partial synchrony, authenticated Byzantine consensus still needs 3t + 1 (DLS 1988, Table I).
• “The 3m + 1 bound is about network partitions, or about FLP.” It is neither. It is a counting result in a synchronous, reliable-delivery model (A1 explicitly assumes every sent message is delivered), and it holds even with unbounded rounds of exchange. FLP is a separate result about a single crash under full asynchrony. Mixing them up produces the very common non-sequitur “PBFT needs 3f + 1 because of FLP.”
• “OM(m) is exponential in n.” It is factorial in m and polynomial of degree m + 1 in n: up to (n − 1)(n − 2) ⋯ (n − m − 1) messages, over m + 1 rounds. For m = 1 that is 6 relayed messages at n = 4. The blow-up is driven by the fault budget, not by the group size alone.
• “The m + 1-round cost is an artifact of this particular algorithm.” No: Fischer & Lynch (1982) proved m + 1 rounds is a lower bound for any algorithm assuring interactive consistency with m faulty processors.
• “Byzantine faults are exotic and rare.” Arbitrary behavior includes not just malice but software bugs, memory corruption, and misconfigured nodes that emit inconsistent data — which is exactly why SIFT, a safety-critical avionics project with no adversary, needed Byzantine tolerance in the first place.
• “The commander is a special trusted role.” No — the commander itself may be the traitor (Scenario B). The protocol protects the loyal lieutenants regardless of which node, including the source, is faulty.

See Also

• Practical Byzantine Fault Tolerance — PBFT; the first protocol to realize 3f + 1 Byzantine agreement efficiently in an asynchronous system, safe without timing assumptions and live under partial synchrony.
• Consensus as a Coordination Game — what changes when the faulty nodes are replaced by self-interested ones with utility functions: the BAR model, incentive compatibility, and where the game framing genuinely adds insight over the fault-tolerance framing used here.
• FLP Impossibility Result — the companion impossibility (deterministic asynchronous consensus with even one crash fault); distinct from the 3m + 1 bound in fault model, timing model, and conclusion.
• Failure Models in Distributed Systems — where Byzantine sits relative to crash-stop, omission, and crash-recovery faults.
• Paxos High-Level and Raft — crash-fault-tolerant consensus needing only 2f + 1 nodes; the cheaper regime when nodes cannot lie.
• Two-Phase Commit — an atomic-commit protocol that assumes no Byzantine behavior and blocks even under a single coordinator crash.
• Distributed Systems MOC — §5 Consensus and Atomic Broadcast.