Byzantine Generals Problem

The allegory poses several generals of the Byzantine army, geographically separated, who must agree to attack or retreat together. They communicate only by messengers, and some generals or messengers may be traitors spreading contradictory information. The question is whether the loyal generals can reach a common agreement despite the traitors. The key theoretical result: consensus is achievable if more than two thirds of participants are honest, meaning the system tolerates up to f Byzantine faults with n greater than or equal to 3f plus 1 nodes.

The problem was formalized by Leslie Lamport, Robert Shostak and Marshall Pease in the paper The Byzantine Generals Problem, published in ACM Transactions on Programming Languages and Systems (TOPLAS), volume 4, number 3, July 1982, pages 382 to 401. The term Byzantine fault tolerance (BFT) originates here. With n equal to 3 and 1 traitor, agreement is impossible using only unsigned oral messages; with signed, unforgeable messages, tolerance improves.

It is the framework from which the entire BFT field derives, already defined in this glossary. The problem is the framing, Byzantine fault tolerance is the property that solves it, and pBFT, Tendermint or HotStuff are concrete implementations. PBFT (Castro and Liskov, 1999) was the first efficient practical solution; Tendermint and CometBFT, the basis of Cosmos, offer instant finality tolerating fewer than one third of Byzantine validators. Satoshi Nakamoto solved a permissionless variant via proof of work in 2008.