The Byzantine Generals Problem
This problem was first described in 1982 by Leslie Lamport while he was working for the defense and space state order. (Though Lamport himself states that the same problem was described before him in SIFT project in Stanford. Anyway he is the author of description with the generals that gave the problem its name).
The problem is based on the presumption that any component of a system can not only go down but afterwards can continue to give the incorrect responses to a query. This can lead to the conflicts between different parts of the system. A trusted system has to be able to resolve such conflicts.
The problem expressed abstractly in the following way:
A group of generals each commanding a portion of army encircle a city. The generals can only communicate sending messengers but they have to reach an agreement. In its simpliest form, the generals must decide only whether to attack or to retreat. Some of them may be the traitors who do not want others to agree on a common decision. So the generals need to have an algorithm that will not allow the traitors to be an obstacle for the others in finding a correct common decision.
The loyal generals will follow our algorithm and the traitors can send arbitrary messages.
It is evident that each general will have to send a message to the others. In order to find a correct decision everyone needs to rely only on the messages from the loyal generals. These messages shall be the same for all generals.
So the task is basically the following: the message shall be send in such a manner that it will be the same for all loyal generals and they can accept it if the sender is loyal himself. To be more precise lets define it in a following way:
- Minimum task: all loyal generals shall follow the same order if the sender is bribed and sends the different messages.
- Maximum task: if the sender is loyal, all loyal recipients shall follow his order.
In his article Leslie Lamport suggests three different solutions of the problem:
Solution I - Oral messages
If we are talking about the oral messages, so more than two thirds of the generals shall be loyal. If there are three or less generals and one of them is the traitor, the probem does not have a solution. Indeed, if one of the generals receives two different messages he can not tell who is the traitor.
We suppose that according to the message exchange algorithm the messages do not get lost and are not fake.
In this case the decision-making algorithm shall be the following:
1. The first general sends a message with his decision to the others.
2. Each recipient then forwards the received message to all other generals except one who originally sent the message.
3. The algorithm is repeated for each general.
So every general has a list of the identical messages.
If one of those who forwarded the message is the traitor, he will be easy to detect because his message will differ from the majority of mesages. In this case the most frequent value shall be chosen as it will be the correct one. So the maximum task will be accomplished as all generals will follow the same order.
If the sender of the message is the traitor, he can send different orders to the others. But in this case everyone will also have the same list of messages! The loyal generals then can follow the algorithm predefined for this case. So the minimum task will be accopmlished as the order from the traitor will be the same for everyone and it will not lead to the disagreement.
Solution II - Signed messages
For this task we introduce the extra conditions:
- A signed message can not be faked. The recipient will reveal the falsification.
- The recipient can understand who signed the message.
So the algorithm will be the following:
- The first general signs and sends his decision.
- Next recipient adds a message to a value array if there is no such a message already.
- Then he signs the message and forwards it to everyone except the sender.
- The algorithm is repeated for each general.
As a result every general gets an array of all versions of the signed orders. If a sender is a traitor, it will be seen, as there will two different versions of an order signed by the same general. In this case every loyal general shall apply a function to a list of a received values that returns a value common for all.
Such a decision has an advantage: the problem can be solved even if there are three generals. So now for decision-making only two thirds of the generals shall be loyal. Indeed, two generals can now understand who is the traitor and can follow the common decision predefined in the function.
Both solutions function only in the case of the fully-connected communications where every participant can send a message to any participant and the messages do not get lost.
Solution III – Lost messages
Now lets make the task more complicated.
Now the generals can not exchange messages directly.
The algorithm that was used for the oral messages can be modified taking in account the changed conditions. Now in order to send a message each general will have to find an array of nonintersecting paths to a recipient. If the messages are oral like in the first solution, then the number of such paths equals 2m+1, where m stands for the number of traitors. Indeed, in order to guarantee sending of a message, the recipient have to get the real order. m number of messages can be lost, then m number of them can be fake, so 2m+1 describes the minimum of paths for guaranteed sending.
The solution with the signed messages can be modified as well for this case. As a result an extra condition is introduced: we need to subtract the number of intermediaries who perform the delivery from the allowed number of traitors. So if the message is delivered in d number of steps and the number of traitor equals m, so the minimum number of general equals n = 3(m+d-1).
In order to choose what order from the pool of the received messages shall be followed the algorithm is used that filters all suspicious intermediaries if different orders have the same signature. As a result there is only one order left and either it or no order shall be followed and for this case the action is predefined by default.
Initially when the problem was first described it was used for a rather limited application types: aircraft avionics and spacecraft equipment, ABM systems. In fact the only way to protect the system from a component failure is to duplicate the component and choose the result using the majority rule. This scheme is based on the presumption that all nonfaulty components give the same results that means the input data must be the same. In order to ensure this condition the above mentioned solutions of the Byzantine General Problem were supposed to be used.
A bit later the suggested solutions were formalized in a form of the protocols, for instance, Paxos protocols. The development of mass technologies brought the same problem to other fields so various consensus protocols were invented for different conditions and application fields. Finally, the interest to the problem grew with the emergence of many blockchain platforms as for them the search for the consensus between the malfunctioning components using different approaches and algorithms is a key task.