What is the Byzantine Generals' problem?
What is the Byzantine Generals' problem?
The Byzantine Generals' problem refers to the game theory problem. A group of generals attacks a fortress; every general has an army and surrounds a fort from one side. Every general has a preference about whether to attack or retreat. It has to be a coordinated attack or retreat to incur minimum losses. Thus, a consensus is held, and the majority decision is implemented. This consensus is formed after following the following steps:
- Every general sends their own choice to all other generals.
- After receiving the choice of all generals, every general calculates the votes in favor of attacking and retreating.
- If the majority is in favor of retreat, then they retreat; otherwise, they attack.
Suppose there is a traitor general who sends a retreat message to half generals and an attack message to the other half generals. Then half of the generals may end up attacking while the other half will retreat, causing the army to lose.
The following slides show all the scenarios of a successful attack, a successful retreat, and an unsuccessful attack.
Application
- Blockchain: In blockchains, we've got a network of nodes (generals), and they have to decide whether to add a block to their journal or not. All the nodes must make the same decision (either to add the block or not) to maintain a constant state of the blockchain across all the nodes. Otherwise, every node will have a different view of the blockchain, making it hard to maintain the network.
- Distributed systems: In data centers, we have a lot of servers to handle user requests. All these servers have their data; if a user request results in a change in data, then all the servers need to update their data(to keep the data consistent across all the servers). If some servers(generals) fail or send the wrong information at this point, this may bring down the whole system.
