Using the Killing of three Kingdoms to talk about distributed algorithms, comfortable?

preface

“SGS” is a popular card game, combining the background of The Three Kingdoms period in China, with identity as a clue, in the form of cards, puzzle and leisure, suitable for all ages.

At the end of the Eastern Han Dynasty, Yuan Shao, as the leader of the alliance, joined forces with eighteen vassals to attack Dong Zhuo.

Before that, let’s talk about distributed protocols and algorithms in general.

Nowadays, many developers have some experience in how to use distributed components and know the general meaning of CAP theory and BASE theory. But very few people really look at distributed algorithms, for three reasons:

Worried that the algorithm is too complex, so it takes very little time.
There are fewer resources on the web that can articulate distributed algorithms in plain English.
There is no clear path to learning distributed algorithms.

I will explain the principles of distributed algorithms and what the learning path is like in a story and plain language in a future article.

Learning path

The way to learn distributed protocols and algorithms is to learn the four basic theories as a foundation, and then learn distributed protocols and algorithms, just like building a house on the foundation. When the foundation is well laid, more solid high-rise buildings can be built.

Four basic theories

Question of the Byzantine general
Theory of CAP
Theory of ACID
The BASE theory of

Eight distributed protocols and algorithms

Paxos algorithm
Raft algorithm
Consistent Hash algorithm
Gossip protocol algorithm
Quorum NWR algorithm
FBFT algorithm
POW algorithm
ZAB agreement

For reasons of length, this paper deals only with the Byzantine generals.

Question of the Byzantine general

You may have heard of the Byzantine general problem. It’s a fundamental problem in point-to-point communication, developed by Leslie Lambert,

Byzantium was the capital of the Eastern Roman Empire in what is now Istanbul, Turkey. Because of the vast territory of the Byzantine Empire, armies were kept far apart for defensive purposes, and generals had to rely on messengers to carry messages from one another. In times of war, all the generals and adjutants in the Byzantine army had to agree on whether they had a chance to win before attacking the enemy’s camp. However, there may be traitors and enemy spies in the army, this is the Byzantine fault tolerance problem.

In fact, Byzantine problem is the most complex fault-tolerant model in the distributed field. Once we understand it, we can master the solution idea of distributed consensus problem, help us understand common consensus algorithm, and also help us choose the appropriate algorithm in our work, or design the appropriate algorithm.

Why is the first fundamental theory the Byzantine general problem?

Because it abstracts well from the consensus problems that distributed systems face. Five of the eight distributed algorithms mentioned above are related to the Byzantine problem, so understanding the Byzantine problem will make it easier to learn other algorithms later.

Now I’m going to explain the Byzantine general problem using identity cards from the Killing of three Kingdoms game.

Three Kingdoms kill id card

There are four main identities in the Killing of The Three Kingdoms: Lord, loyal minister, traitor and traitor. Each player gets an id card. There is only one Lord. 2 loyal officials at most, 4 rebels at most, and 1 mole at most.

master

Victory conditions: eliminate all traitors and spies

Technique: take their own survival as the primary goal to distract the attention of anti-thieves. Cooperate with the loyal to destroy the rebels and determine who is loyal and who is inside.

Loyal subjects

Terms of victory: Destroy all rebels and spies while keeping the Lord alive.

Skill: loyalty is the Lord’s barrier, deterring counterthieves and traitor balance.

The thief

Winning conditions: eliminate the master can win.

Technique: As the most numerous identity, the counterparty needs to focus its firepower on attacking the enemy’s weak spots. Right thinking is the key to winning.

mole

Winning conditions: first eliminate rebels and loyal ministers, and finally with the Lord single challenge to become the last sole survivor.

Technique: correct tactics + cool head + luck.

Return to the Byzantine problem

At the end of the Eastern Han Dynasty, Yuan Shao, as the leader of the alliance, joined forces with eighteen vassals to attack Dong Zhuo. With Dong Zhuo as the traitor, Yuan Shao as the Lord, and two loyal men and a traitor, the three men were chosen: Cao Cao, Liu Bei and Sun Jian (Sun Quan’s father). The traitor played the role of a loyal minister, and the Lord and the two loyal ministers did not know the identity of the traitor, so they were treated as loyal ministers.

! [Game 3 vs 2]

Dong Zhuo was very powerful. He had excellent xiliang troops and lu Bu, the god of war, under his command. We all know the story of Lu Bu at the Sanying station. Lu Bu had one strong match against Liu Bei, Zhang Fei and Guan Yu.

In order to kill Dong Zhuo, Yuan Shao must unify the loyalist’s battle plan, three loyalists do not know what other huahuachangzi, there is a mole. What if the traitor secretly communicated with dong Zhuo, the traitor, and sent misleading information to loyal officials? What if the letters were intercepted or the messages in the letters were replaced? These scenes could disrupt the battle plan, ending with loyalists attacking and loyalists retreating. Then the rebels can take advantage of this opportunity to attack, one by one.

Yuan Shao did not have cao cao’s tact, so how did he get his loyal ministers to reach a consensus and develop a unified battle plan?

The mapping above is a simplified representation of the Byzantine general problem, and yuan Shao is now facing a typical consensus problem. The idea is to use appropriate communication mechanisms to allow multiple generals to reach consensus and develop a coherent battle plan in the face of potentially misleading information.

One side chose to retreat

Liu Bei, Cao Cao and Sun Jian used messengers to send messages about whether to attack or retreat, and then negotiated whether to attack or retreat. Majority rule is followed and no abstention is allowed.

Cao Cao suspicious more heavy, reconnaissance the terrain of the rebels, decided to retreat. Liu Bei and Sun Jian decided to attack.

Liu Bei decided to attack and sent a messenger to Cao Cao and Sun Jian to attack.
Cao Cao decided to retreat and sent messengers to Liu Bei and Sun Jian to withdraw.
Sun Jian decided to attack and sent a messenger to Cao Cao and Liu Bei to attack.

Cao Cao received information: attack 2 votes, one of their own retreat votes, votes than one, attack vote: retreat vote = 2:1, according to the majority rule of the above vote, Cao Cao will attack. Then the plan of battle of the three parties is to attack, so it is a consistent plan of battle. He defeated Dong Zhuo at last.

Enter the mole. – Retreat

Because of our early setting, Sun Jian, as a traitor, had already communicated with the traitor Dong Zhuo privately and would not attack dong Zhuo.

Liu Bei decided to attack and sent a messenger to Cao Cao and Sun Jian to attack.
Cao Cao decided to retreat and sent a messenger to tell Cao Cao and Sun Jian to retreat.
Sun Jian decided to retreat and sent messengers to Cao Cao and Liu Bei to withdraw.

Liu Bei received one vote to attack and one vote to retreat, but he himself chose to retreat. Therefore, liu Bei got the following votes: attack: retreat = 1:2. In accordance with the principle of the minority obeying the majority, Liu Bei chose to retreat at last.

An inside job. – One step forward, one step back

The spy saw the above plan and found that the loyal ministers had retreated and not been destroyed, so he wanted to destroy one of them by cheating.

Liu Bei decided to attack and sent a messenger to Cao Cao and Sun Jian to attack.
Cao Cao decided to retreat and sent a messenger to tell Cao Cao and Sun Jian to retreat.
Sun Jian, acting as a traitor, sent a messenger to tell Liu Bei to attack and Cao Cao to retreat.

So what are the results?

Liu Bei had two votes to attack and one to withdraw, while Cao Cao had one vote to attack and two votes to withdraw. According to the principle that the minority is subordinate to the majority, Liu Bei will finally choose to attack, while Cao Cao will choose to retreat. Sun Jian, as a traitor, will certainly not attack. Liu Bei alone attacked the rebel Dong Zhuo, but he was weak and killed by Dong Zhuo.

In this scene, we see that the traitor Sun Jian easily interferes with the battle plans of Liu Bei and Cao Cao by sending misleading information, resulting in the two loyal ministers being defeated one by one. This phenomenon is the dilemma of loyalty and judgment. So Lord Yuan Shao how to solve this problem?

Solution of the Byzantine problem

Solution principle

Even Yuan Shao participated in the vote, thus increasing the number of a loyal minister. Three loyal ministers and one traitor. The four generals then made a pact to follow a default order, such as retreat, if no order was received. In addition, procedures are agreed upon to send operational information and how to execute operational instructions. The key point of this solution is to carry out two rounds of battle information negotiation.

Let’s see what we did in the first round.

The first step: the general who sends the battle information first is called commander (Yuan Shao), and the other general is called adjutant (Liu Bei, Cao Cao, Sun Jian).
Step 2: The commander sends his operational message to all his lieutenants.
Step 3: Each adjutant takes the combat information he receives from the commander as his own combat instruction; If no operational message is received from the commander, the default retreat will be taken as the operational order.

We use the figure to demonstrate: Yuan Shao as the main duke first sent combat information, combat command for attack. Then Cao Cao, Liu Bei and Sun Jian received orders to attack.

Let’s see what we did in the second round.

The commander of the first round (Yuan Shao) has sent the order, and now liu Bei, Cao Cao and Sun Jian are required to send the battle information to the other two deputy generals as commanders in turn.
The three deputies would then follow the rules of majority rule and carry out the orders they received.

Sun Jian cheated. – Two retreat

If Sun Jian cheated, for example, he sent evacuation messages to Cao Cao and Liu Bei, as shown in the picture below. Then liu Bei and Cao Cao received two votes to attack and one vote to retreat. In accordance with the principle of minority obeying the majority, Liu Bei and Cao Cao finally carried out the attack, realizing the consistency of the battle plan, cao Cao and Liu Bei jointly defeated the rebel Dong Zhuo (even though Sun Jian did not take part in the battle).

Sun Jian cheated. – One advance, one retreat

If sun chien cheats, send cao cao retreat instruction, to attack liu bei sends instructions, so liu bei received combat information is attacking three votes, is bound to attack, attack and combat information is cao cao received two votes, retreat 1 vote, finally, cao cao will attack, so liu bei and cao cao still beat against the thief dong zhuo joint operations.

It seems that the introduction of one commander can indeed prevent Sun Jian from cheating, but what if Sun Jian is the commander in the first round and the others are the adjutants?

Sun Jian as the commander

In the first round sun Jian sent evacuation instructions to one of the adjutants, Yuan Shao, and the other two adjutants, Cao Cao and Liu Bei, to attack. So the result of the first round is as follows:

In the second round, Sun Jian took a rest, and the other adjutants began to send instructions to other adjutants according to the instructions sent by Sun Jian.

Cao Cao sent instructions to Liu Bei and Yuan Shao to attack.
Liu Bei sent instructions to Cao Cao and Yuan Shao to attack.
Yuan Shao sent orders to Cao Cao and Liu Bei to retreat.

As shown in the figure below, at last Cao Cao, Liu Bei and Yuan Shao received two votes to attack and one vote to retreat. According to the principle of majority rule, all three of them launched the attack. Carried out a consistent battle plan to ensure the victory of the battle.

summary

From the above demonstration, we know how to solve the Byzantine general problem. In fact, Lambert also mentioned how to solve this problem in his paper.

If the number of defectors is M and the number of generals n >= 3m + 1, then the Byzantine general problem can be solved.

Prerequisite: The number of defectors is the same, m + 1 round of negotiation is required.

This formula, you just need to remember it, push to the process can refer to the paper.

For example, in attacking Dong Zhuo as mentioned above, among cao Cao, Liu Bei and Sun Jian, Sun Jian was a traitor who could cheat and make the battle plan inconsistent. A loyal minister, Yuan Shao, had to be added to negotiate a consensus in order to agree on a battle plan.

Byzantine solution ii – Signature

How could Byzantium’s dualistic problem be solved without increasing the number of loyalists?

Solution two is to sign the message. For example, generals communicated with each other through seals, tiger symbols and other tokens. To ensure these characteristics:

The signature cannot be forged, and any changes to the content of the signed message will be detected.
Anyone can verify the general’s signature.

Due to the limitation of space, the demonstration of signature will not be expanded here. If you are interested in @me, it will be added later.

conclusion

Explain the distributed consensus scenario through the killing of The Three Kingdoms. How do they map to distributed systems?

General corresponds to the computer node.
Loyal generals correspond to normal computer nodes.
Defecting generals correspond to computer nodes that are malfunctioning and sending misleading information.
When a messenger is killed, communication fails and information is lost.
Couriers replaced by spies correspond to communications that have been maliciously attacked, forged or hijacked.

Don’t underestimate the Byzantine problem, which is the most complex failure scenario for distributed scenarios. For example, these knowledge points are useful in the blockchain technology of digital currency. And the Byzantine Fault Tolerance (BFT) algorithm must be used.

Byzantine fault-tolerant algorithms, FBFT algorithms, PoW algorithms, we’re not going to talk about them in this paper, we’ll talk about them later. One bite doesn’t make a man fat

With Byzantine error tolerance, there must be non-Byzantine error tolerance, which is, as the name implies, no nodes that send misleading information. CFT algorithm is to solve the consensus problem in the case of distributed system with faults but no malicious nodes. In simple terms, the message may be lost or repeated due to system failure, but there is no error message, forged message. The corresponding algorithms are Paxos algorithm, Raft algorithm, ZAB protocol. Follow up ~

There are 5 algorithms mentioned above, and all of them are related to the Byzantine problem. Do you think the Byzantine problem is important today?

How do you choose from so many algorithms?

Trusted nodes, choose non – Byzantine fault – tolerant algorithm. Otherwise, use Byzantine fault-tolerant algorithms, such as THE PoW algorithm used in blockchain.

Shoulders of giants: Distributed Protocols and algorithms, Geek time

I am Wukong, strive to become stronger, become super Saiya people! I have written a set of Spring Cloud advanced tutorial and PMP brush small procedures. Welcome to our public account: Wukong chat structure