In essence, the distributed consistency problem can be understood from two dimensions: one is how to reach a unanimous decision on a certain value; The other is how to reach an agreed sequential decision on a series of consecutive values. Obviously, if we can find a solution to problem one, then problem two will be solved. Let’s start with a small problem in life and see how to design a reasonable algorithm to solve problem one.
There is such a family, which consists of six members, they are father, mother, grandparents, sister and a 3-year-old brother. On this day, we have to decide what color hat our brother will wear on the trip tomorrow. Since the five parents are in different places at this time (distributed system), they can only communicate through WeChat (partially synchronous network). We try to dissect a simple consensus problem through such a case.
A single point of failure
Since the goal is to make a unanimous decision, the simplest way is to find the person with the highest public trust who is responsible for making a decision that everyone can agree on. For example, we always choose our mother’s decisions because she is usually in charge of our younger brother’s clothes. However, if you have to wait for your mom’s proposal for every decision, it is inevitable that sometimes your mom’s phone will be disconnected, such as when your phone is turned on in airplane mode during a flight. Therefore, it is not good to always choose one person to make the decision. This is a classic single point of failure problem where the entire cluster is blocked because of a single participant.
The minority is subordinate to the majority
Since a single person can’t be trusted to make decisions, the most obvious solution is majority rule. That is, every decision must be approved by at least half of the people. Of course, we are not taking into account the fact that there are people who vote indiscriminately, sending different votes to different people (Byzantine error). In the current scenario, for the proposal value to be chosen, at least 3 out of 5 people need to accept the same proposal. And we need to make sure that once one proposal value is selected, there is no possibility that another proposal value will be selected later on.
Note: Here chosen is a global view, while accept is a single person view, that is, the same person may accept multiple proposals, but the entire group can ultimately choose only one proposal value.
Bring scenario 1
In order to complete the final decision, we stipulate that everyone must accept the first proposal he or she receives. In this way, everyone’s positive heart can be aroused. If you want your proposal to be passed, you must quickly come up with a color and send out the proposal.
However, such a scheme can lead to a dilemma in which the decision cannot be made. As shown in the picture above, the father raised the red hat and felt more positive energy! And timely to the proposal of private stamp to the mother, mother also readily accepted. Almost at the same time, Grandpa brought up the blue hat and felt more retro! And timely to the proposal private stamp to grandma, grandma also gladly accepted. My sister thought green was more fashionable, but when she sent the message out, she found that everyone had already made their own choices. The result was a 2-2-1 situation, with no proposal reaching more than half (>=3). As a result, we found that some people may have to accept multiple different proposals if they want to make the final decision.
Bring scenario 2
In this case, let’s consider a scenario where each person accepts all proposals he receives.
This time, we will only consider the two people who initiated the proposal, namely my father’s red proposal and my sister’s green proposal. If my father’s proposal has been approved by 3 votes and reached the selected state, then my sister will initiate the proposal. According to the principle that everyone accepts all proposals, the green proposal can also reach the selected state in the end. Obviously, this scheme violates the principle of uniqueness, and if it keeps running like this, it may not be able to choose a proposal value.
At this point, we found a problem, that is, dad’s red proposal now that has reached the state selected in advance, so we can let the elder sister before the proposal to make sure all people under the state, if have reached a consensus on a proposal value half node (i.e., up to the selected state), then sister can stop making proposals, Or send another proposal with the same proposal value to ensure uniqueness. Would that solve the problem?
Bring scenario 3
Scenario 2 problems still exist, as shown in the above, father and sister were identified in advance if all people under state was in a state of not to vote, and in turn their proposal, because dad is private stamp respectively, so the message has a certain delay, and sister directly pulled a group chat disposable notice to grandpa and grandma, Therefore, my sister’s proposal reached the selected state before my father’s proposal. Later, when my father’s proposal was notified to my mother and grandpa, how should they make a decision?
Through the above problems, we found that in order to prevent the decision to enter a state of not end, we also need to somehow prioritize, proposal to refuse some old, ineffective proposal, and timely feedback to the proposal acceptable proposal value, avoid the plan has been initiated the same proposal. That is to say, if the grandfather, when he received the delayed proposal from his father, could know that there was an updated proposal (sister’s proposal) before and reject the old proposal, and inform his father that he has accepted the green proposal from his sister, the dilemma of multiple proposals reaching the selected state could be avoided.
For example, we could assign a series of proposal numbers to each of the five people. The proposal numbers would be incremented as follows:
At the same time make the following provisions:
A proposal consists of proposal value color and proposal number seqNo, which can be expressed as (color, seqNo).
Each person kept track of the largest proposal number they received and rejected any proposal with a smaller proposal number
When a proposer receives a proposal that has been accepted, he or she must accept the proposal unconditionally or risk being trapped in a cycle of endless proposals
Each proposal needs to be completed in two stages, namely, pre-inquiry stage (PREPARE) and final confirmation stage (ACCEPT). The inquiry stage is used to determine a serial number value SEQNO and timely detect whether there is an accepted proposal value, and the confirmation stage is used to determine a proposal value COLOR. The solution of Scenario 1 is relatively simple, that is, after the consent message of the majority of people cannot be received within a certain period of time (asynchronous network), we try to launch a proposal again with a new proposal number, until a proposal message can be successfully conveyed to the majority of people (synchronous network), and the decision can be completed. Let’s take a look at how to resolve scenarios 2 and 3.
Note: In the figure below, P n represents the prior inquiry message, asking other nodes whether they accept proposal number N; R(V, N) represents the response message, informing the proposer of the currently accepted maximum proposal number and proposal value; A(v, n) represents the final confirmation message, telling other nodes to try to finally confirm A proposal value v, whose proposal number is n.
Scenario 2 solution
For proposals that have reached their selected status, we can ensure that subsequent proposals will not overwrite the original proposal values.
At this point, the proposal decision-making process is as follows:
Dad used Proposition 1 to initiate an inquiry
Dad, Mom and Grandpa all agree on Proposition 1 and feedback that no proposal value has been received at present. Proposition number defaults to 0 (empty vote).
Since the majority of people (>=3) agreed, the father sent the final confirmation message to the majority of people. The proposal number is 1 and the proposal value is red. At this time, red has actually reached the selected state
My sister uses Proposition 5 to initiate an inquiry
Since the proposal must be approved by at least three people, and the three people selected must have an intersection with those who agreed with the father’s proposal before (for example, grandpa), so the people in the intersection can timely feedback the proposal that has been agreed before, that is, Red Proposal No. 1, while the rest still feedback empty voting
After waiting for the feedback result from most people, my sister found that some proposals had been agreed by others, so she chose the proposal value with the highest proposal number (red) and covered her own proposal value (green).
Sister sends the final confirmation message. The proposal number is 5 and the proposal value is red
In the end, everyone accepted the red proposal, although the proposal number may vary
Scenario 3 solution
For proposals that have not reached the selected status, if a new proposal is proposed, the final selected proposal value may be in one of two cases.
In the first case, the new proposer is able to discover the old proposal value and eventually chooses the old proposal value.
In the second case, the new proposer is unable to discover the old proposal value and eventually chooses the new proposal value.
Scenario 3-1 solution
The new proposer is able to discover the old proposal value and eventually chooses the old proposal value.
At this point, the proposal decision-making process is as follows:
Dad used Proposition 1 to initiate an inquiry
Dad, Mom and Grandpa all agree on Proposition 1 and feedback that no proposal value has been received at present. Proposition number defaults to 0 (empty vote).
Since the majority of people (>=3) agreed, Dad sent the final confirmation message, but due to the delay of the message, the final confirmation message was only sent to Dad and Grandpa. Mom delayed receiving the message, so red is not actually selected
My sister uses Proposition 5 to initiate an inquiry
Since the proposal must be approved by at least three people, if one of the selected three people happened to have accepted the final confirmation message from father (for example, grandfather), he would immediately feedback the proposal that had been agreed before, that is, the Red Proposal No. 1, and the other people would still feedback the empty vote
After waiting for the feedback result from most people, she found that some proposals had been agreed by others, so she chose the proposal with the highest proposal number (red) and covered her own proposal value (green).
Sister sends the final confirmation message. The proposal number is 5 and the proposal value is red
My mother delayed receiving the final confirmation message from my father. Since she did not receive a proposal with a larger proposal number, she also accepted the red proposal
In the end, everyone accepted the red proposal, although the proposal number may vary
Scenario 3-2 solution
The new proposer is unable to discover the old proposal value and eventually chooses the new proposal value.
At this point, the proposal decision-making process is as follows:
Dad used Proposition 1 to initiate an inquiry
Dad, Mom and Grandpa all agree on Proposition 1 and feedback that no proposal value has been received at present. Proposition number defaults to 0 (empty vote).
With the consent of the majority (>=3), Dad sends the final confirmation message, but because of the delay in the message, the final confirmation message is only sent to Dad and Mom. Grandpa delayed receiving the message, so red is not actually selected
My sister uses Proposition 5 to initiate an inquiry
Since the proposal must be approved by at least three people, if none of the three chosen people happened to have accepted the final confirmation message from father, the sister would receive empty votes from three people
Since most people (>=3) agreed, my sister sent the final confirmation message to most people. The proposal number is 5 and the proposal value is green. At this time, the green has actually reached the selected state
My mother delayed receiving the final confirmation message from my father. Since she had accepted the proposal with a larger proposal number before, she refused to accept my father’s old proposal value and timely fed back the new proposal value to my father
Dad, after receiving the rejection response message, will try to restart the proposal from scratch, and finally choose the green proposal
In the end, everyone accepted the green proposal, although the proposal number may vary
To sum up, in order for the decision to converge, we have imposed some constraints explicitly or implicitly:
1. Everyone’s mobile phone needs to be online in real time (that is, there can be no downtime, dropped line and other non-Byzantine errors) and any WeChat message can be received within a certain time delay (synchronous network model). When there is a network disconnect scenario, consensus may not be reached
2. Everyone should make a proposal/vote in strict accordance with the above rules, no random proposal/vote action (Byzantine act).
The above is actually using the principle of the classic distributed consistency algorithm Paxos. Paxos, however, solves only the most basic consensus problem: how to agree on a decision value in a non-Byzantine synchronous network environment. What if the system enters an asynchronous network environment (e.g., Mom’s cell phone has no signal)? What if there is a Byzantine node (e.g., grandpa deliberately voted red for dad and green for sister)? The whole problem becomes much more complicated when we take this series of problems into consideration.
Fortunately, predecessors have provided us with a lot of theoretical basis, in order to deal with different problems, there have been a lot of excellent consensus algorithms. If you are interested, there will be a detailed introduction to the classification of consensus algorithms, which will comprehensively show the choice and trade-off of consensus algorithms in different scenarios.
Add little assistant orange (18458407117) to join the technical exchange group. Welcome to share your views with us and discuss the infinite future of blockchain
Consensus Algorithm Research Group of End Haoqu Chain Technology Foundation Platform Department