Byzantine Generals Problem

The problem

Imagine several armies of the Byzantine Empire besieging an enemy city. The generals leading each army can communicate only by messenger, and all of them must agree on the same plan, attack or retreat (if only half attack, they will be wiped out). But among the generals are traitors, who tell one general "attack" and another "retreat," sending different messages to different recipients. The problem is whether, in this situation, all the loyal generals can agree on the same plan without a small number of traitors distorting the agreement.

The metaphor is military, but what is being modeled are computer nodes or processes. A failed node may not simply stop responding; it may send corrupted data, return different values to different recipients, or pretend to behave normally, taking any behavior whatever. Such failures are called "Byzantine faults."

Main results

The paper gave two central results. One is the theorem that, when messengers deliver messages orally (that is, there is no way to prevent forgery or tampering), if there are m traitors, agreement is impossible unless the total number of participants satisfies n ≥ 3m+1. In other words, the problem becomes unsolvable once traitors make up a third or more of the whole; even the smallest case, three generals and one traitor, cannot reach agreement.

The other is the result that, if unforgeable signed messages can be used, agreement is possible no matter how many traitors there are. Once "who said what" can be proven in a form that can be forwarded to third parties, the difficulty of the problem changes qualitatively. This contrast plainly shows the role cryptography plays in distributed consensus.

Origin of the name

The fable was at first told as a story about the generals of the Albanian army, but since this risked portraying a real country as a group of traitors, it was replaced at Jack Goldberg's suggestion with the Byzantine Empire, which had already fallen. As a result, "Byzantine" became established as a term in distributed systems, giving rise to derived terms such as Byzantine fault and Byzantine fault tolerance (BFT).

Applications and reach

In the control systems of aircraft and spacecraft, the system as a whole must keep working correctly even when some of its redundant computers or sensors produce abnormal values, so this problem setting has been treated as an actual design requirement. PBFT (Practical Byzantine Fault Tolerance), published in 1999 by Miguel Castro and Barbara Liskov, achieved practical performance under the condition n ≥ 3f+1, turning Byzantine fault tolerance from theory into something that could be implemented.

Since 2009 it has again been widely cited in the context of blockchains. The task of keeping the contents of a ledger consistent while assuming that anyone can join or leave and that malicious parties may be among them has the same structure as the Byzantine Generals Problem^※1.