Byzantine General Problem
Imagine that the grand Eastern Roman empire aka Byzantine empire has decided to capture a city. Alas, there is fierce resistance from within the city. The Byzantine army has completely encircled the city. The army has many divisions and each division has a general. The generals communicate between each as well as between all lieutenants within their division only through messengers.
All the generals or commanders have to agree upon one of the two plans of action. Exact time to attack all at once or if faced by fierce resistance then the time to retreat all at once. The army cannot hold on forever. If the attack or retreat is without full strength then it means only one thing — Unacceptable brutal defeat.
If all generals and/or messengers were trustworthy then it is a very simple solution. However, some of the messengers and even a few generals/commanders are traitors. They are spies or even enemy soldiers. There is a very high chance that they will not follow orders or pass on the incorrect message. The level of trust in the army is very less
Consider just a case of 1 commander and 2 Lieutenants and just 2 types of messages- ‘Attack’ and ‘Retreat’.
In Figure 1 — The Lieutenant 2 is a traitor who purposely changes the message that is to be passed to Lieutenant 1. Now Lieutenant 1 has received 2 messages and does not know which one to follow. Assuming Lieutenant 1 follows the Commander because of strict hierarchy in the army. Still, 1/3rd of the army is weaker by force as Lieutenant 2 is a traitor and this creates a lot of confusion.
However what if the Commander is a traitor (as explained in Figure 2). Now 2/3rd of the total army has followed the incorrect order and failure is certain.
In Figure 3 and Figure 4, we have just added 1 more Lieutenant and 1 more type of message (Let’s say the 3rd message is ‘Not sure’). Immediately the complexity of finding a consensus between all the Lieutenants and the Commander is increased. Now imagine the exponential increase when there are hundreds of Lieutenants.
This is Byzantine General Problem. It is applicable to every distributed network.
