PAPERS-12-003 · Paper — The Byzantine Generals Problem

The paper

The Byzantine Generals Problem, written by Leslie Lamport, Robert Shostak, and Marshall Pease in 1982 and published in the ACM Symposium on Operating Systems Principles, is a landmark because it formalized the hardest kind of agreement problem and gave the first precise conditions for tolerating arbitrary (Byzantine) faults.

Before this paper

Before this work, fault‑tolerance research assumed that faulty components simply stopped working – the so‑called crash faults. Researchers did not have a model for components or attackers that could keep running while sending conflicting, misleading information to different peers. This gap left a wall: there was no understanding of how to achieve agreement when some participants could behave arbitrarily and lie.

The key idea

The authors imagined a group of generals surrounding a city who must all decide to attack or retreat, even though some generals might be traitors sending contradictory orders. Their key insight was that agreement is possible only if the number of honest participants exceeds two‑thirds of the total, which translates to needing at least 3f+1 nodes to tolerate f Byzantine failures.

How it works

Each general first broadcasts its own order to every other general. Loyal generals then forward (relay) the messages they received, attaching the identity of the sender, so that every participant eventually gathers a tree of messages showing what each general heard from every other. After enough rounds – specifically f+1 rounds – each loyal general examines the collected messages, discarding any inconsistent reports, and applies a majority rule to decide on the final order. Because honest generals exchange consistent information, the contradictions introduced by traitors are outvoted, leading all loyal generals to the same decision.

See it — agreeing despite traitors

flowchart TD
  A["Loyal generals<br/>must agree"] --> B["Some traitors<br/>send conflicting msgs"]
  B --> C["Need 3f+1 nodes<br/>to survive f traitors"]
  C --> D["Honest majority<br/>reaches one plan"]

What they showed

The paper proved an impossibility bound: with unsigned messages, agreement cannot be achieved with fewer than 3f+1 participants for f Byzantine faults. It also presented algorithms that achieve agreement exactly when the system has at least 3f+1 nodes, confirming that more than two‑thirds honest participants are sufficient.

What it changed

This result turned Byzantine fault tolerance into a rigorous foundation for building high‑assurance systems. It showed that distributed agreement could survive deliberate lies, not just crashes, and it inspired decades of research into robust protocols, eventually becoming the theoretical core of blockchain consensus mechanisms and safety‑critical voting systems in aircraft and spacecraft. Next: The Morris Worm.

The one-line takeaway

You need at least 3f+1 participants to tolerate f arbitrary (Byzantine) failures.

Read it / meet it

Reading the original paper gives you a clear view of how the classic message‑relay algorithm works and why the 3f+1 bound is tight. Its legacy lives on in every blockchain and in safety‑critical voting systems that rely on Byzantine agreement today.