Byzantine Generals Problem

The problem is framed as a group of Byzantine army generals, each commanding a division, who must agree on a common battle plan (attack or retreat). Communication is via messengers, but some generals may be traitors who send conflicting messages to different generals. The challenge is to ensure that loyal generals agree on a plan even if traitors actively try to disrupt the consensus.¹

Lamport et al. proved that to tolerate m traitors, the system must have at least 3m+1 generals. They presented the Oral Messages algorithm (OM(m)) that achieves consensus in m+1 rounds, with message complexity O(n^m+1). They also introduced the concept of signed messages, which reduces the requirement to 2m+1 generals, as signatures prevent traitors from forging messages.²

The Byzantine Generals Problem is not just a theoretical puzzle; it has direct applications in real-world systems. In aerospace, NASA and the military use Byzantine fault-tolerant systems in aircraft and spacecraft control, where a single failure can be catastrophic. For example, the Boeing 777's flight control system uses triple redundancy to tolerate Byzantine faults.

In modern computing, the problem underpins blockchain technology. Bitcoin and other cryptocurrencies solve a variant of the Byzantine Generals Problem through proof-of-work, where consensus is achieved by computational effort. More efficient algorithms like Practical Byzantine Fault Tolerance (PBFT) are used in permissioned blockchains and distributed databases.³

Several variants of the problem address different constraints. The Interactive Consistency problem requires all loyal generals to agree on the same vector of decisions, even if some are traitors. The Byzantine Agreement problem focuses on reaching a single value. These variants have different lower bounds and algorithms.⁴

Another important variant is the Asynchronous Byzantine Agreement, where messages can be delayed arbitrarily. Fischer, Lynch, and Paterson proved that in an asynchronous system, consensus is impossible if even one process can fail (the FLP impossibility result). This has profound implications for distributed system design, leading to the development of randomized algorithms and partial synchrony models.

The problem's name was inspired by the Byzantine Empire's complex politics, but the original paper also considered a more mundane scenario: two generals besieging a city, which illustrates the impossibility of reliable communication over an unreliable channel.¹

One lesser-known fact is that the problem was first posed in 1978 by Lamport in a memo titled "The Byzantine Generals Problem," but the 1982 paper formalized it. The paper is among the most cited in computer science, with over 10,000 citations. Additionally, the problem has connections to the Two Generals Problem, which is a simpler version that is also unsolvable in an unreliable network.⁵

In the 1990s, researchers developed Byzantine fault-tolerant state machine replication, which allows systems to continue operating correctly even when some components fail maliciously. This work, led by Miguel Castro and Barbara Liskov, produced the PBFT algorithm, which is now widely used in enterprise blockchain platforms.⁶

Byzantine fault

A fault in which a component behaves arbitrarily, including sending conflicting information to different parts of the system.

Consensus

The process of reaching agreement among distributed processes on a single value or plan.

Oral messages

Messages that cannot be forged, but can be relayed and altered by traitors.

Signed messages

Messages that include unforgeable signatures, preventing traitors from altering content.

FLP impossibility

The result that consensus is impossible in an asynchronous system with even one faulty process.