The Byzantine Generals Problem (Lamport, Shostak & Pease, 1982)

Leslie Lamport, Robert Shostak and Marshall Pease, ACM TOPLAS Vol. 4, No. 3, July 1982, pp. 382–401, written at SRI International. 20 pages. The paper the f < n/3 bound in consensus comes from, read here in full from the author’s own PDF.

Generals camped around a city must agree on a battle plan using messengers, while some unknown subset of them are traitors who may say anything at all. The two conditions to satisfy are stated once and used throughout:

IC1. All loyal lieutenants obey the same order. IC2. If the commanding general is loyal, then every loyal lieutenant obeys the order he sends.

They are called the interactive consistency conditions, and the paper’s last section shows they are not a metaphor.

The bound, and where it comes from

With oral messages — defined by three assumptions, that every message sent is delivered (A1), the receiver knows who sent it (A2), and the absence of a message can be detected (A3) — three generals cannot tolerate one traitor. The proof is two pages and depends on nothing but the definitions: a loyal lieutenant cannot distinguish “the commander lied to the other lieutenant” from “the other lieutenant is lying about what the commander said.”

That result then does all the work. Any solution for 3m or fewer generals could be used to build a three-general solution by having each of the three simulate at most m of them, so no solution with fewer than 3m + 1 generals exists. The bound is not a property of an algorithm; it is a property of the problem.

Algorithm OM(m) is the matching solution: recursive, each round demoting to OM(m−1) with one fewer participant, terminating at a majority vote. It works for 3m + 1 or more generals and it is expensive — up to (n−1)(n−2)…(n−m−1) messages, and message paths of length m + 1. The paper notes Fischer and Lynch proved that path length is unavoidable, so OM(m) is optimal in latency if not in traffic.

Signatures do not improve the bound, they delete it

Add assumption A4 — a loyal general’s signature cannot be forged, and anyone can verify it — and Algorithm SM(m) solves the problem for any number of generals and any number of traitors. No three-to-one ratio, no minimum. A lieutenant collects properly signed orders into a set, relays them, and if the set ever holds two different orders the commander is provably a traitor.

This is worth stating more strongly than a summary usually does. consensus currently records that “authentication changes the bound,” from podc-lecture-notes. The primary source says the bound disappears: the entire 3f+1 replica count exists to compensate for a node’s ability to tell different lies to different peers, and an unforgeable signature removes that ability outright.

Connectivity, when everyone cannot reach everyone

Sections 3 and 4 assume a complete graph. Section 5 drops it, and the two algorithms diverge sharply. OM(m) generalises to OM(m, p) and needs the graph to be 3m-regular — which at the minimum 3m + 1 generals means completely connected anyway. SM(m) extends to the weakest possible connectivity: with at most m traitors and the loyal subgraph connected with diameter d, SM(m + d − 1) works. Signatures buy topology freedom as well as the resilience bound.

The part that is usually left out: this is about hardware

Section 6 is where the generals stop being a story. The motivating system is majority voting over redundant processors — the paper names redundant computing sites in a ballistic-missile-defence system, and the SRI context is avionics.

Majority voting only produces a reliable answer if every non-faulty processor votes on the same input, and a single faulty input device defeats that on its own. The example given is physical rather than adversarial: a faulty input unit can put a marginal signal on a shared wire that some processors read as 0 and others as 1, and two processors reading a clock as it advances get different times from a perfectly good clock. The authors’ conclusion is flat:

“There is no way to guarantee that different processors will get the same value from a possibly faulty input device except by having the processors communicate among themselves to solve the Byzantine Generals Problem.”

IC1 and IC2 are then re-read as the two conditions majority voting needs, with the input unit as commander and “loyal” meaning non-faulty. The word “traitor” was never about malice. A component that is merely broken in an unhelpful way produces the same problem, which is why the model outlived its avionics origin.

Two admissions the paper makes about its own assumptions

Both are in Section 6 and both matter more than the algorithms for anyone applying this.

A3 rests on synchronized clocks, and clock synchronization is the same problem. Detecting a missing message means timing out, which needs a known message delay and clocks synchronized to within a fixed bound. Keeping clocks synchronized when some processors are faulty is, in the authors’ words, “as difficult a problem as the Byzantine Generals Problem itself” — deferred to a future paper. The assumption that makes the oral-message algorithms work is not free; it is the same problem wearing a different hat.

A4 can never actually be guaranteed. A signature is just data, so a faulty processor could in principle emit a valid one; the property “no faulty processor can generate S_i(M)” is achievable only probabilistically. The paper splits the cases: against random malfunction a randomizing function gives a 1/P forgery chance, and against malicious intelligence — explicitly, “a perfectly good processor being operated by a human who is trying to disrupt the system” — it becomes a cryptography problem, cited to Diffie–Hellman. Byzantine fault tolerance and adversarial security part company at exactly this line.

The closing sentence is the one for this spoke

“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.”

Every operational database in this wiki takes that discount. Assuming crash-stop failure — a node stops rather than lying — is what makes Raft and Paxos affordable, and it is a purchase, not a default. It holds up under hardware faults and network partitions, and it is the wrong assumption when a node is corrupted rather than dead.

Provenance

T1 — the primary paper, from Lamport’s own publications page, extracted locally from the PDF rather than summarized from a secondary account. The link the source arrived on carried a Facebook fbclid tracking parameter, stripped here. The paper is 44 years old and its results are permanent; freshness: stable.

consensus (the concept page this is the primary source for) · podc-lecture-notes (the secondary account that reached this spoke first) · consistency-models · database-sharding · operational-databases · leslie-lamport

Cross-spoke: ../research-wiki holds tla-plus, Lamport’s later specification language, and owns the formal-methods lineage. The seam is Lamport himself — one node, linked from both.