Anyone who knows about Bitcoin and blockchain has more or less heard of the Byzantine General problem, or that one of bitcoin’s (or blockchain’s) major achievements was solving the Byzantine General problem. But not many people really understand the problem, or even know the nature of the problem. This paper is a technical popular science, will focus on the Byzantine general problem itself to the essence and classical algorithm analysis, and discuss some related problems. The author refers to a lot of literature, including a large number of illicit goods, but does not propose a new algorithm to solve the problem, which is not the purpose of this paper.
Part1: What was the problem with the Byzantine general
The Byzantine Generals Problem is a consensus Problem: first proposed by Leslie Lamport and two others in 1982, it is called The Byzantine Generals Problem or Byzantine Failure. The core description is that there may be traitors in the army, but to ensure the consistency of attack, which extends to the field of computing, developed into a fault tolerance theory. With the advent and rise of Bitcoin, this famous question has re-entered the public consciousness.
1.1. Byzantine Generals problem scenario
A brief informal description of the Byzantine generals is as follows:
The Byzantine Empire wanted to attack a powerful enemy, so it sent 10 armies to surround it. This enemy was no match for the Byzantine Empire, but it was strong enough to withstand a simultaneous attack by five regular Byzantine armies. For some reason, these 10 armies could not be grouped together for a single point of breakout, but had to attack simultaneously in separate sieges. There was no chance that any one army could attack the enemy country unless at least six armies attacked simultaneously. They were scattered around the enemy country and depended on the signalmen to communicate with each other to negotiate the intention of attack and the timing of attack. The trouble with these generals is that they are not sure if any of them are traitors, who may change their intentions or timing of attack. In this state, could the Byzantine generals find a distributed protocol that would allow them to negotiate remotely to win the battle? This is known as the Byzantine general problem.
It should be made clear that the Byzantine general problem did not consider whether the signalman could be intercepted or could not convey the message, i.e., the channel of the message was completely unquestioned. Lamport has demonstrated the impossibility of trying to achieve consistency through messaging over unreliable channels where messages can be lost. So, in the study of the Byzantine general problem, we have assumed that there is no problem with the channel, and on this premise, to do consistency and fault tolerance related research. If the need to think about channels is problematic, it brings up another related issue: the military-to-military problem.
1.2. Issues related to Byzantine generals: Inter-military issues
As has been said before, the Byzantine general question and the two armies question are essentially different. A large number of domestic articles explaining the Byzantine general issue confused the two, which in fact confused the essence of the two issues, resulting in a lot of misunderstanding. The two questions do seem somewhat similar, but the premise and research direction of the questions are completely different.
As shown in Figure 1, the White troops were stationed in the ditch, while the Blue troops were scattered on either side. The White army is more powerful than any blue army, but the Blue army can defeat the White army if they attack together. They could not communicate remotely and had to send signalmen across the ditch to tell the blues to negotiate attack times. Whether there is a communication protocol that will make the Blues win is the question of the two armies.
See here you may find that the two militaries and Byzantine generals problems have certain similarity, but we must pay attention to is that the operators have to through the enemy’s trench, was arrested in the process he may be, that is to say, the problems of the two militaries channel is not reliable, and not one of them traitors said, this is the two militaries and Byzantine generals problems fundamentally different. Thus, a large number of articles that confuse the Byzantine general problem with the bi-military problem do not fully understand both.
The fundamental problem lies in the unreliability of the channel. Conversely, if the channel that transmits the message is reliable, the two-military problem can be solved. However, there is no such channel, so the two-military problem is unsolvable in the classical context. Why?
If Blue Army No. 1 (abbreviated as 1) sends signal troops to Blue Army No. 2 (abbreviated as 2), if 1 wants to know if 2 has received his message, 1 must ask 2 to send him a receipt saying “I have received your message, and I agree to your proposal to attack tomorrow morning at exactly 10:09”.
However, even if 2 had sent this message, 2 could not be certain that 1 would attack at this time, because the receipt sent by 2 could not be received by 1. So, 1 must send another receipt to 2 saying “I received”, but 1 will not know if 2 received such a receipt, so 1 will expect another receipt from 2.
As ridiculous as it may seem, there is always a need for a return receipt in this system, and it is not always possible to achieve full confidence on either side. What’s more, we haven’t considered the possibility that the signalman’s messages could be tampered with. Thus it can be seen that under the classical situation, the two military problems are unsolvable, and there is no communication protocol that can make the Blue army a certain victory.
Unfortunately, the military-to-military problem is a problem that must be solved in modern communications systems, and we can’t completely solve it, which means that you and I can still lose, listen to, or tamper with messages. But can we solve most cases in a relatively reliable way? This involves talking about TCP. In fact, search for “Military-to-military issues and three-way handshakes” and you’re bound to find a lot of TCP related content. If you are an expert in communication, please bear with me that there may be some burrs in popularizing the principles and limitations of TCP in a simple and understandable way.
In TCP protocol, A sends A random number x to B first. After B receives x, IT sends another random number Y and x+1 to A as A reply. In this way, A knows that B has received it, because it is not possible to crack random number X. And then A sends back y plus 1 to B, so B knows that A has received it. In this way, A and B establish A reliable connection, each trusting that the other has received and confirmed the message.
In fact, A doesn’t know if B received y+1; In addition, due to the unreliability of the channel, x or Y may be intercepted, these problems show that even the three-way handshake can not completely solve the problem between the two armies, but under the condition of controllable cost, we regard TCP protocol as a practical solution to the problem between the two armies.
So, can we find a theoretical way to really solve the problem between the two armies? The answer is yes, the quantum communication protocol, I do not have the ability to understand this rather profound question. As I understand it, two particles in a quantum entanglement state can synchronize with each other no matter how far apart they are, an effect that intuitively can be used to enable secure communication.
But because of the uncertainty principle, when a particle’s state is measured it changes, so another message must be sent over an unreliable channel. Although the “other message” is unreliable, there is already an absolutely reliable channel (quantum entanglement), which ensures that the message is reliable even if the other channel is unreliable. Otherwise, at least the stolen message can be detected.
So we can believe, at least in theory, that the two-military problem is solvable, that there is a way to ensure the reliability of information transmission even if unreliable channels are used. So, with the channel secured, we can go back to the Byzantine generals.
Part2: The substance and formalization of the problem
We have looked at the scenario of the Byzantine general problem, and it is clear that the solution to this problem is based on the fact that the signalman can communicate the message correctly, that is, the channel is absolutely reliable. At the same time, through the previous discussion of the military-to-military issues, we understand that theoretically credible channels can also be realized. Next, we will explore the essence of the Byzantine general problem.
2.1. The essence of the Question of the Byzantine generals
Reviewing the problem, a group of generals want to achieve a certain goal (attack or retreat together), but acting alone does not work. The generals did not know how to reach agreement because of the traitors. Notice that consistency is what the Byzantine general question is about, and if there are already too many traitors to solve the problem, this is the question of rebellion; At the same time, the goal is for the loyal generals to reach agreement, and for the loyal generals to attack or retreat, as long as they reach agreement.
But will consensus alone solve the problem? Consider that, if everything was ready, every loyal general would objectively have won if he had attacked, but they “unanimously” did not attack because of the traitors; On the other hand, the generals were not supposed to attack, but all “united” because of the traitors.
It can be seen that “consistency” alone is not enough to solve the Byzantine general problem, we also need to propose a “correctness” requirement. This requirement is worth considering, because there may be an “absolute right” judgment if we look at it objectively, but the judgment may vary from general to general. How do we define “right”? We may simply say that correctness means that every loyal general expresses himself correctly, and does not reject his message because a traitor makes other generals think that a loyal general is a traitor.
At this point, we have simplified the Byzantine general problem to the point that all loyal generals were able to convince other generals of their true intentions and eventually act in undivided agreement; The formal requirements are consistency and correctness.
If the problem is generalized, the algorithm for consistency and correctness does not require the command to be “attack/retreat” or “1/0”, but “send message 1/ send message 2/ standby” or “X/Y /z/ W”. This means that the Byzantine General problem algorithm can provide inspiration for a variety of distributed systems. Like a power system or a network.
It follows that the problem boils down to an algorithm of consistency and correctness for loyal generals, since traitors can make any judgment that goes beyond convention. We’re just trying to find an algorithm that doesn’t interfere with the traitors. To solve this algorithmic problem, we need to externalize the formal requirements.
2.2. Deduction of formal conditions
Define a variable vi (without loss of generality, vi is not required to be a Boolean) as the value of the ith general’s command received by other generals; General I will take his judgment as VI. As you can imagine, the vi values received by each general are not necessarily the same due to the presence of traitors. After that, define a function to handle vectors (v1,v2… ,vn) represents the majority opinion, and generals use the result of this function as their final command. At this point, we can use these definitions to formalize the problem to match consistency and correctness.
1) Consistency
Condition 1: Every loyal general must get the same (v1,v2… ,vn) instruction vector or instruction set.
This means that the loyal general does not necessarily use the message sent by General I as VI, and General I may also be a traitor. But depending on this condition alone, the message sent by the loyal general may also be modified, which will affect the accuracy.
2) Correctness
Condition 2: If general I is loyal, other loyal generals must use the value he sends as vi.
In this way, we obtain the formal condition of consistency and correctness (condition 1 and condition 2), which is sufficient condition. Considering that the correctness condition is for a single general and the consistency condition is for all generals, we rewrite the consistency condition for convenience as
Condition 1 ‘: Any two loyal generals use the same VI regardless of whether general I is loyal or traitor.
Condition 1 and condition 1 prime are exactly equivalent. This is a very clever step conversion, such consistency conditions (1 ‘) and correctness condition (2) involves only a general I how to accept his help other general sent out the value of the vi, so you can change the question to the commander – adjutant model to simplify the problem, that is, a commander convey own command to an adjutant, n – 1 makes:
IC1: All loyal lieutenants obey one command, consistency.
IC2: If the commander is loyal, every loyal adjutant follows the orders he gives, that is correct.
IC1 and IC2 are derived from condition 1 ‘and condition 2 respectively. The commander-adjutant model can become a complete problem by simply iterating the commander over the generals, and they can use exactly the same algorithm. IC1 and IC2 sufficient conditions to solve the problem of the Byzantine generals, in this mode, the commander lieutenant in the form of a consensus means that under the commander’s orders has been effectively convey, if the objection, launch a new commander general objectionable as commander adjutant model seeks to express their ideas, a negotiated agreement.
Next, we can discuss the algorithm of the Byzantine general problem. As long as the algorithm can satisfy IC1 and IC2, it means that the algorithm can effectively solve the Byzantine general problem.
In the classic case, we can find two ways, oral agreement and written agreement. The author will discuss the deduction and proof of the two algorithms one by one. The proof part will not adopt pure reasoning, but mainly introduce the proof idea.
In fact, if the algorithm is fully deduced, you can already have a general understanding of the algorithm. Oral agreement and written agreement will have many different inspirations, the implementation of oral agreement is simple, but the algorithm is complex, at the same time need to overcome more difficulties; The written protocol algorithm itself is simple and can overcome many problems, but implementing the algorithm is not easy. These differences lead to different usage scenarios and implementations.
Part3: Oral agreement
First, let’s be clear about what an oral agreement is. We refer to oral agreements that meet the following three conditions:
A1: Every message sent can be delivered correctly
A2: The receiver of the message knows who sent the message
A3: Able to know missing messages
In short, the channel is absolutely trusted and the source is knowable. Note, however, that verbal agreements do not reveal the last source of information.
Conclusion: oral agreement is used, if the number of traitors is less than 1/3, the Byzantine general problem is solved. That is, if the number of traitors is M, the problem is solvable when the total number of generals n is at least 3m+1 (that is, IC1 and IC2 are satisfied).
This result shows that a system with three-mode redundancy can tolerate only fault-freeze type errors, in which a component freezes after failure (that is, the result of a known error), and that three-mode redundancy is sufficient.
But for the Byzantine general problem, because of the variety of decisions traitors can make, a four-mode redundant system is required to be fault-tolerant. A verbal protocol algorithm is one that tells its orders to others and draws its conclusions by taking a majority of others’ orders. It should be noted, however, that orders from other generals are determined by algorithmic recursion. Using this method, it is possible to ensure that the loyal general can meet the requirement of consistency and correctness, i.e. solvable problem, when the number of traitors is less than 1/3.
So how can the oral protocol algorithm be fault-tolerant with less than 1/3 of the traitors? Next, the author will introduce the oral protocol OM(M) algorithm proposed by Lamport in his paper. The author will introduce the detailed content, example deduction and proof of oral protocol algorithm one by one. This part will require you to spend some time to think about.
3.1. Oral Protocol algorithm OM(M)
OM (0) algorithm
(1) The commander sent his orders to each adjutant.
(2) Each adjutant takes orders from the commander; If no command is received, it defaults to retreat.
OM (m) algorithm
(1) The commander sent his orders to each adjutant.
(2) For each I, vi is the order each adjutant I receives from the commander, and if no order is received, it defaults to an order to retreat. Adjutant I sends it as the starter in OM(M-1) to the other N-2 adjutants.
(3) For each I, and for each j ≠ I, vj is the command sent by adjutant I from adjutant J in step 2 (using OM(m-1) algorithm). If no command from adjutant J in step 2 is received, it is the default retreat command. Last adjutant I uses majority(v1,… , vN-1) get the command.
Among them, the majority (v1,… , vN-1) represents the command of most people. If it does not exist, it defaults to the retreat command.
It’s not easy to read the algorithm all at once, and it took me quite a bit of time to figure it out. But don’t worry, I’ll explain a few noteworthy points and use a simple example to help you understand the algorithm.
(1) The algorithm always guarantees a more secure default value, which means that if the message is not transmitted, it is known and the transmission time is not considered.
(2) This algorithm is a recursive algorithm, and OM(M-1) is needed in OM(m) to obtain relevant results. M is the number of traitors, from m to 0, which means that for each general, it takes m+1 rounds of the algorithm to complete.
(3) The algorithm is about M, which means that the algorithm must know how many traitors there are. In other words, using this algorithm, the Byzantine general problem can be solved when the number of traitors is below a certain maximum (i.e., 1/3 of the total number of generals).
(4) For any k
This is the meaning of recursion, and if you feel that I am not making it clear, don’t worry, just remember that each step involves a number of steps, and then you will understand the core idea of the algorithm in the example deduction.
3.2. Deduction of oral agreement examples
First, I will use an example of m=1, n=3 to illustrate the problem of three-mode redundancy, and show how the system is fault-tolerant when m=1, n=4, so that you can see that the algorithm is running. However, since the recursive process is not reflected when m=1 (because m-1 becomes 0), the author will give another example of m=2 and n=7 to illustrate the recursive process of the algorithm. (1) m=1, n=3 case n=3, means that one commander sends orders to two adjutants, m=1 means that one of them is a traitor. First consider the case where the commander is loyal and the adjutant 2 is a traitor.
(Figure 4: m=1, n=3: Commander loyal and adjutant 2 traitor)
The commander passed the command to the two adjutants 1 and 2 to attack, but since adjutant 2 did not want them to agree, he changed the commander’s order to retreat. So for Adjutant 1, how should he judge? He could not tell whether the commander was a traitor or the adjutant was a traitor.
(Figure 5: m=1, n=3 commander is a traitor)
If the commander is a traitor and the two adjutants are loyal, the commander will send two different orders. When the two adjutants checked their orders, they were confused again, unable to tell whether the commander was a traitor or the other was a traitor, and thus unable to tell. This case illustrates very simply that three-mode redundancy is not dynamically fault-tolerant. (2) m=1, n=4, n=4, means that one commander sends orders to three adjutants, m=1 means that one of them is a traitor. First consider the case where the commander is loyal and the adjutant 3 is a traitor.
(Figure 6: m=1, n=4, commander loyal and adjutant 3 traitor)
If the commander sends each adjutant A message of attack (A) in OM(1), then on OM(0), the traitor adjutant 3 tells adjutant 1 and adjutant 2 that he has received A message of retreat (R). Then for adjutant 1 (or adjutant 2), his message vector after combining commander, adjutant 3, and adjutant 2 (or adjutant 1) will be (A,A,R). After using the majority function,A will be adopted, satisfying IC1 and IC2 (recall IC1: all loyal adjutants obey one command, IC2: If the commander is loyal, every loyal adjutant obeies the orders he gives.
(Figure 7: m=1, n=4 commander is a traitor)
If the commander is a traitor, then we don’t need to satisfy IC2. For convenience, let’s assume that the rebel Commander will send the three lieutenants A message of (x,y,z) in OM(1), where x,y, and z can be either A or R. The three loyal lieutenants will then exchange the information they receive, as OM(0) requires.
For adjutant 1, his message vector will be (x,y,z) when he combines commander, adjutant 2, and adjutant 3. It can be seen that for the other two loyal adjutants, their message vector will also be (x,y,z). Majority (x,y,z) is the same for the three, no matter how x,y,z changes, so the three adjutants will take the same action.
(3) m=2, n=7 and then we’re going to talk about m=2, n=7, which is just one more traitor, but it’s a recursive process, so it’s a lot more complicated.
First, let’s discuss the commander’s loyalty situation, assuming the traitors are adjutants 5 and 6.
(Figure 8: m=2, n=7: Commander loyal and adjutant 5 and adjutant 6 traitor)
In OM(2), the commander passes the attack order (A) to the various adjutants. In OM(1), loyal lieutenants will send the message they receive (A), but since lieutenants 5 and 6 are traitors, they will send something else (e.g. R). At this point, loyal lieutenants will use the method in OM(1) to identify each V1 to v6. For example, if adjutant 1 receives an order from the commander, does he simply use the majority function to synthesize the message from the commander and other generals? He can’t, because it’s still in OM(1), he doesn’t know if the commander is A traitor or not, he will confirm the general’s order by asking others, but the algorithm will pass the commander’s order to others as v1 (v1=A).
Then he will try to get other v2-v6 values, which are already in OM(1). Adjutant 1 will not easily believe the information from others, such as adjutant 2 sending him command A, but he will doubt the information from Adjutant 2, so he uses OM(1) to ask others what adjutant 2 has sent them. Adjutant 3 and adjutant 4 honestly tell Adjutant 1 that Adjutant 2 is sending them A, and adjutant 5 and adjutant 6 are going to lie again, and they’re going to say, let’s assume they’re sending x ‘and Y’. In this way, OM(0) is finally entered, and adjutant 1 will synthesize the feedback of other adjutants on v2 to get the vector (A,A,A,x ‘,y ‘). By using the function of majority, v2=A is obtained. In the picture below, this is the information that Adjutant 1 gets from OM(1) (x, y, etc., represent indeterminate commands).
(Figure 9: Adjutant 1’s information in OM(1) when commander is loyal)
We can obtain that adjutant 1’s v1~v6 vectors are (A,A,A,A,x,y). Using the function majority, adjutant 1’s final action will be A. Similarly, we can see that the command vector obtained by several other loyal lieutenants is (A,A,A,A,x,y), and the action taken by using the majority function is A. Thus, we can see that the loyal adjutant’s command is A (satisfy IC1) and is consistent with the loyal general’s command (satisfy IC2). At this point, you should have an idea of how recursive the algorithm is, and whatever m is, it’s just a matter of how many steps the algorithm takes. As for the commander is a traitor situation, in fact, is similar, here simply mentioned again for easy understanding. If you already understand the algorithm, you can skip it.
(Figure 10: m=2, n=7 commander and adjutant 6 are traitors)
For convenience, we assume that adjutant 6 is a traitor. The commander in OM(2) sends different commands (A,R,A,R,A,x) to adjutants 1 to 6. In OM(1), each adjutant sends out the order he receives, and (for convenience, presumably) adjutant 6 sends (A,R,A,R,A) to the other adjutants. Similar to the foregoing, considering adjutant 1, after taking the command A from the commander as V1, he will also inquire the command from others to confirm v2~v6. Similarly, we express it as the following figure:
(Figure 11: Adjutant 1’s information in OM(1) when the commander rebelled)
As shown in the figure, we can get that the v1~v6 vector of adjutant 1 is (A,R,A,R,A,A). Using the function of majority, the final action of adjutant 1 will be A. Similarly, we can see that loyal adjutant 1 to adjutant 5 get the message vector (A,R,A,R,A,A), and eventually they will take the action of A (meeting IC1), while the commander is A traitor and does not need to meet IC2. Note that if adjutant 6 passes (R,A,R,A,R), then they all get (A,R,A,R, R), and the number of A and R is the same. This does not mean that the majority is not working. , vN-1) represents the command of the majority of people, and if it does not exist, it defaults to the retreat command), all actions will adopt R, which is also satisfied.
So far, we have gone through the examples of the oral algorithm thoroughly, if you are still interested, you can try to see why there is no agreement when n=7, m=3, the operation is similar. 3.3 Oral protocol algorithm proof algorithm proof idea is not complicated, simple, for a recursive algorithm, we use mathematical induction to prove is the most intuitive and effective method. Let’s review the proposition: the total number of generals is N, the number of traitors is M, OM(m) can be realized, in the case of n>3m, such that:
IC1: All loyal lieutenants obey an order.
IC2: If the commander is loyal, every loyal adjutant obeies the orders he gives.
To prove the whole proposition, we introduce a lemma for IC2:
Lemma: For any m and K, if there are more than 2K +m generals and at most K defectors, then the algorithm OM(m) satisfies IC2.
Proof:
(1) m=0, while the general is loyal, which directly satisfies IC2;
(2) m>0, assuming that OM(m-1) is valid, then only the round of OM(m) needs to be considered.
N > 2 k + m, means that the n – 1 > 2 k, n – 1 is all except commander adjutant, and all the adjutant more than twice the number of a traitor, and that they directly use the majority function, can directly get the commander ordered correctly. As you can see, this lemma says that if you only consider IC2, you don’t need 3 times as many generals as there are defectors. So let’s go back to the statement.
Proof:
First consider the commander is loyal, let k=m in the lemma, directly obtain OM(m) can satisfy IC2.
At this point, we have only to consider the commander as a traitor. We also use mathematical induction.
(1) m=1, we have previously deduced that OM(1) can satisfy the case of 1 traitor commander and 3 loyal adjutants;
(2) m>1, then assuming n ‘>3m’, OM(m-1) can satisfy IC1 and IC2.
Since the commander is a traitor, in OM(m) the commander issues orders to various adjutants, among whom there will be M-1 traitors. In the next round, the number of adjutants is at least 3m, the number of traitors is M-1, obviously 3m>3(m-1), that is to say n ‘>3m’, according to the hypothesis, OM(M-1) can satisfy IC1 and IC2, even though the commander is a traitor, since OM(M-1) is valid, OM(m) loyal adjutants get the same (v1,… , vN-1) vector, so the loyal adjutant will use the same command using the majority function, verified.
To sum up, we always ask for the same thing in the oral agreement (v1,… Vn minus 1 vector, as long as this vector is the same, we can do whatever we want with it. Since the algorithm is recursive, we must make the processing method universal and logically effective. That is why we choose the algorithm of majority function. This is crucial but not intuitive because our first reaction is to get the same value of the majority function. A majority of functions have the same value (v1,… Is vn minus 1 the same vector? Understanding the idea of recursion correctly is the key point of using this algorithm and proving it by mathematical induction.
So far, we have a rough idea of what verbal agreements are, what can and can’t be done, and the derivation and proof of this algorithm. Many systems will have the situation of oral agreement, that is, each system node can send their own message accurately, and can know the source of the message. However, this method does not allow messages to be traced back to the source, which makes verbal agreements at least quad redundant. We could try to find a way to make messages traceable to the source, which could conceivably broaden the conditions of use. This method could be a written agreement.
Part4: Written agreement
We have discussed a lot in oral agreement, revealing that the disadvantage of oral agreement is that the message cannot be traced back to the source, which makes oral agreement must be in the condition of four-mode redundancy to ensure correctness. But what if we introduced a way to trace messages back to their source? This is where written agreements come in.
In addition to A1, A2 and A3, we add a condition A4 to the oral agreement to make it a written agreement
A4 :(a) signature cannot be forged, once tampered can be found, and the traitor’s signature can be forged by other traitors; (b) Anyone can verify the reliability of the signature.
So, let’s start with the conclusion: for any m with at most m defectors, SM(m) can solve the Byzantine general problem. In other words, in the case of signature, written agreement can break the deadlock of three-mode redundancy, in the case of signature, as long as the number of traitors is known, we can use SM(M) algorithm to solve the Byzantine general problem.
4.1. Written Protocol Algorithm SM(M)
We’ve talked a lot about oral protocol algorithms, so I’ll try to make a brief introduction to written protocols. review
IC1: All loyal lieutenants obey one command, consistency.
IC2: If the commander is loyal, every loyal adjutant follows the orders he gives, that is correct.
We need to find an algorithm SM(m) that, regardless of the total number of generals n and the number of traitors M, the loyal generals will always be consistent (satisfy IC1 and IC2) if we use this algorithm. We use set Vi to represent the set of commands received by adjutant I, which is a set, that is, a set that meets the conditions of mutuality (no repeating elements) and so on. Similarly, we define the choice(V) function to determine the choice of each adjutant. This function can take many forms, as long as it satisfies the following two conditions:
(1) If the set V contains only one element V, then choice(V)= V
(2) Choice (O)=RETREAT, where O is an empty set
Any function that satisfies both of these conditions can be used as choice(), for example by taking an average. We just need to define choice() on a case-by-case basis. This is not important, but you can think for yourself. Later we will find that SM(m) algorithm is not a recursive algorithm, as long as we make each adjutant receive the same V set, choice(V) will also be able to get the same value.
The algorithm is briefly explained as follows:
Initialize Vi= empty collection.
(1) The general signs orders and issues them to each adjutant;
(2) For each adjutant I:
(A) If adjutant I receives A V :0 message from the originator and no other command sequence has been received, then he
(I) make Vi {v};
(ii) Send V :0: I to all other adjutants.
(B) If adjutant I receives a message of the form V :0:j1:… :jk message and v is not in set Vi, then he
(I) add v to Vi;
(ii) If k
(3) For each adjutant I, when he receives no more messages, obey the command Choive (Vi).
It is worth noting that if the commander is loyal, since his signature cannot be forged, all loyal adjutants will get a single point set {v}, they adopt the same command set Vi, resulting in choive(Vi) is also v, satisfying IC1 and IC2.
If the commander is not loyal, only IC1 needs to be satisfied, but the algorithm SM(m) causes all loyal lieutenants to get the same Vi, and the command adopted after using choice() must be the same.
4.2. Deduction of written Agreement examples
The situation in which the commander is a traitor is a little more difficult to imagine. For example, n=3, m=1, where the commander is a traitor, is a situation that cannot be resolved by verbal agreement.
(Figure 12: m=1, n=3 commander is a traitor)
Obviously, adjutant 1 gets V1={A,R} and Adjutant 2 gets the same V2={A,R}. They must get the same command when they use the choice function.
Similarly, n=4, m=2, where the commander is a traitor, is also a situation that cannot be resolved by verbal agreement.
(Figure 13: commander and adjutant 3 are traitors in m=2 and n=4)
Adjutant 1 and Adjutant 2 get V1=V2={A,R}, and they get the same command using choice. Even if the command is not a Boolean, a similar conclusion can be reached after the analysis framework above. As for the proof of this algorithm, interested readers can refer to Lamport’s original text without too much explanation. If you have any questions, please contact me.
(Figure 14: Lamport’s proof of written protocol algorithm in his paper)
The essence of a written agreement is the introduction of a signature system, which makes all messages traceable to their source. This advantage, greatly saving the cost, eliminates the requirement of 1/3 of the oral agreement, as long as the written agreement is adopted, the loyal general can achieve the agreement (IC1 and IC2). The effect is striking, but there are obvious drawbacks to oral agreements.
The conclusion of the written agreement is very exciting. Doesn’t that solve the Byzantine general problem? But note that we have actually added some conditions in A1 to A4, which makes the Byzantine general problem solable under these assumptions, but there are some problems in the actual situation. Observing A1~A4, we made some assumptions that are difficult to fulfill in reality, such as not considering the delay time of information transmission, the signing system of written protocol is difficult to realize, and the preservation of signed message records is difficult to exist independently from a centralized organization. In fact, there is a perfect solution to the practical limitations of written protocols: blockchain. If you’re interested, you can also refer to my article in the same series, “Overqualified: Solving the Byzantine Generals Problem with Blockchain.”
Author: Poison poison Cheng Proofread: in early summer tiger village rector: Printemps Source: Babbit Information
