What is Byzantine Generals Problem and How Technology Solves it?
With the advancement of new technology, communication between two entities is not mysterious anymore. We can send and receive messages through the Internet without concerning whether our messages reached to the destination or not. We can travel from one place to another without regarding whether the airplane going to make it or not. Moreover, we can launch rockets to space confidently. All that become possible because of our reliance on our computer systems to be fault-tolerant. Today, airplane engine systems, nuclear power plants, and any other system whose actions depend on the results of many sensors exist due to the fault tolerance that systems provide.
To understand how fault tolerance works, we need to go back in time to look at one problem (two armies, one city) that led to the evolution of today’s technological world.
Two Armies, One City
The problem of the “two general problems” first published in 1975 describing a scenario of a city in a valley, and two armies on the top of the hills on opposite sides, as shown in the figure above. The generals and their troops want to attack the city. However, they need to attack the town at the same time or else they will fail the mission. Each army has a general, and the generals need to communicate with each other to agree on the time of the attack. Nevertheless, the only way for the two generals to communicate is to send a messenger through the valley to send a message to the second general, which is quite risky. The city in the middle may either catch the messenger and throw him in jail, or even worse, replace the messenger with a spy who would deliver a wrong message. For instance, army A wants to attack on Monday at 10 pm. Now, Army A would send a messenger to army B with a message, “we will attack on Monday at 10 pm.” Let’s assume that the messenger went through the city and let’s assume that army B got the message. However, the two armies always would be in a dilemma whether the next army has received my message or not. Therefore, to eliminate the dilemma, the messenger must go back to acknowledge that army B has received the message.
However, army B also needs to receive an acknowledgement from army A that the message has been received. This itself is a problem because there is no way to guarantee each general to be sure the other has agreed on the attack plan. Both generals will always be left wondering whether their last message got through.
Until today the two generals problem has been proven to be unsolvable!
To make it even more interesting, let’s look at the same problem differently!
The Byzantine Generals Problem
Let’s imagine that several divisions of the Byzantine army are camped outside an enemy city, each division commanded by its own general. The generals can communicate with one another only by messengers. After studying their enemies, the generals must decide on a common plan of action. However, some of the generals might be traitors, who will try to prevent honest generals from reaching an agreement.
The generals must guarantee the following attributes:
· All loyal generals follow the same plan of action.
· A small number of traitors should not cause loyal generals to adopt an evil plan.
For the commanders to reach consensus in this case, where lieutenant 1 is a traitor, the value of the majority lieutenant should be taken place.
Theorem: for any m, Algorithm OM(m) reaches consensus if there are more than 3m generals and at most m traitors.
This means the algorithm reaches consensus if 2 out of 3 actors are honest. For instance, in the scenario above, there is one commander and three lieutenants. Only one of the lieutenants is traitor. This means 1/3 of the lieutenants is traitor. In this case, the attack would proceed. Lieutenant 3 would follow the majority vote.
The vote steps would be as following:
· Commander sends attack to L1, L2, and L3.
· L1 sends retreat to L3.
· L2 sends attack to L3.
· L3 considers the majority (attack, attack, retreat).
Let’s look at the case of the commander being a traitor!
The vote steps would be as following:
· Commander is traitor, who sends three different commands to each lieutenant; attack, retreat, and wait.
· L1 sends retreat to L3.
· L2 sends attack to L3.
· L3 receives three different commands (attack, retreat, and wait).
Take a moment here to reflect on the previous scenario where the majority votes would be elected. In this scenario, the commander is the traitor. Therefore, lieutenant 3 receives three different commands. Consequently, lieutenant 3 would take a default action, which is a retreat.
How Does This All Relate to Technology?
We can keep adding complexity to the problem by introducing many traitors. However, the purpose of this problem is to introduce a solution to the current technological world. The world is moving towards distributed systems such as blockchain technology, which provides network decentralization. It crucial to reach consensus in distributed systems since there is no central authority managing the traffic. In Bitcoin blockchain, there are many nodes or miners are involved in confirming transactions across the world. Take a moment to think about what would happen if one or more nodes are “traitors.” In order to a transaction to be confirmed across the blockchain network, the nodes need to reach consensus. The Byzantine generals problem is applied to blockchain technology to prevent traitors to mislead the actions of the honest nodes.
Moreover, Byzantine fault tolerance is a feature that defines a system to be fault-tolerant. Therefore, the Byzantine fault tolerance has been needed in large systems such as airplane engine systems, nuclear power plants, and pretty much any system that relies heavily on sensors communication. For instance, if part of the airplane engines systems stops working or reports wrong information, then the engine would use the Byzantine fault tolerance algorithm to resolves the issue. Therefore, the Byzantine generals problem was crucial to the world’s technological development.
Conclusion
In this article, we have discussed the origin of basic concepts of consensus in distributed systems. In the next article, we will review and compare some the algorithms (PoW, PoS, and DPoS)that are used in blockchains to achieve Byzantine Fault Tolerance.
If you enjoyed the article, please share, comment, and clap 👏 few times for me! Your support will definitely motivate me to produce great content!
