Overview of the Byzantine Generals Problem

A well-known issue in decentralized network systems is the Byzantine Generals Problem (Byzantine Fault). This problem addresses consensus formation in decentralized network systems and was formalized in 1982 by Leslie Lamport and his colleagues:

Leslie Lamport, Robert Shostak, and Marshall Pease, The Byzantine Generals Problem, SRI International, 1982.

Leslie Lamport and the Turing Award

Leslie Lamport received the Turing Award, regarded as the highest honor in computer science, in 2013. The award’s name originates from Alan Turing, known for his work in decrypting the Enigma machine.

Challenges of Consensus Formation in Decentralized Networks

Trustworthiness of Nodes and Conditions for Consensus

In decentralized network systems, there are a finite number of nodes, some of which may be faulty or malicious. To achieve consensus among these nodes, the following two conditions must be met:

1. All honest nodes must agree on the message (value) and terminate.
2. The message (value) must be generated by honest nodes.

Specific Challenges of the Byzantine Generals Problem

The Byzantine Generals Problem questions whether consensus can be achieved among nodes that communicate with each other, even when communication failures or deliberate misinformation by some nodes are possible.

Origin of the Byzantine Generals Problem

The Generals’ Situation

The name of this problem is derived from a metaphor involving generals in the Byzantine Empire. The Byzantine army is divided into units, each led by a general.
These units surround an enemy castle, and it is assumed that communication is limited to one-on-one messages.

Common Plans and the Issue of Betrayal

In this scenario, the castle can only be captured if all units attack simultaneously.
To achieve this, the generals need to agree on a common plan, deciding either to “attack” or “retreat” and conveying their decisions through messengers.

However, some generals may be traitors, deliberately disrupting the formation of consensus among the loyal generals. For example, a traitorous general might alter an “attack” message received from one general into a “retreat” message before passing it to another general.

Risks of Consensus Failure

Due to such acts of betrayal, some generals may receive conflicting messages, such as both “attack” and “retreat.” This could prevent consensus from being reached, causing only some units to attack and leading to the defeat of the Byzantine army.

Goals and Limitations of the Byzantine Generals Problem

The Goal of Loyal Generals

The goal of this problem is to enable all loyal generals to reach consensus on a common plan. Under no circumstances should interference by traitorous generals result in the adoption of an incorrect plan.

Limitations of Consensus Formation

It has been proven that if one-third or more of the generals are traitors, consensus formation becomes impossible.