Previously, “Brief Introduction to distributed CAP Theorem” briefly introduced the inevitable theorem that data exist in distributed system. Briefly, in the process of synchronizing data from one node to another node, data inconsistency will occur before the synchronization is completed, so there must be Partition tolerance at this point. Distributed systems can only choose between Consistency or Availability.

CAP is about distributed consistency, and this time we’re going to talk about distributed consensus. A lot of developers think that consistency and consensus are the same thing, but they’re talking about completely different things.

  • Consistency: Data at point A is synchronized with data at point B, and the data between the two can be consistent.
  • Consensual: After one or more nodes suggest what a value should be, all processes in the system agree on the value in a way that everyone agrees on.

A common scenario for consensus is master selection. For example, when redis master fails, the clustering common consensus algorithm selects a master. Digital currencies such as Bitcoin also require more complex consensus-building algorithms.

Let’s take a step-by-step look at some common algorithms and problems associated with distributed consensus.

Question of the Byzantine general

Leslie Lamport(developer of the paper typesetting system LaTeX and 2013 Turing Prize winner) describes the following system in her paper:

A group of Byzantine generals led a separate army to besiege a city.

In order to simplify the model, the operational strategy of each army is limited to attack or withdrawal. Because a partial attack and a partial withdrawal could be disastrous, the generals had to vote to agree on a strategy of all attacking together or all withdrawing together.

While the generals were on different sides of the city, they could only communicate with each other by Courier. During the voting process, each general sends his or her vote for attack or retreat to all the other generals by Courier, so that each general can decide on a strategy based on his or her vote and the information sent by all the other generals.

The name of this system is the Byzantine General problem. From the description, it is clear that the generals need to vote for a unanimous decision in distributed scenarios using a majority rule algorithm.

In the Byzantine general problem, the default was to assume that the messenger would not be intercepted and that the message would get through. More often than not, there may be traitors among generals, couriers intercepted and faked, and messages never reached. And traitors or couriers posing to maliciously vote for other generals, showing different votes to different generals, thus undermining the consistency of the generals’ execution. Such errors are called Byzantine errors.

A system is said to have Byzantine fault tolerance, or BFT, if it can handle Byzantine generals’ errors.

For example

Suppose there were five generals voting (an odd number of votes is required to form a majority), and one of them was a traitor. Of the four loyal generals, two voted for the attack and two voted for the withdrawal.

At this point, the traitor may deliberately send a message to two generals who are willing to attack, while sending a message to two other generals who are willing to withdraw. So from the point of view of the two generals who voted for the attack, the result of the vote was three to go for the attack; In the opinion of two generals who voted to leave, three voted to leave. The unity of the armies was thus broken, with disastrous results.

Even if all the five generals are loyal, the voting results need messengers to be delivered among the generals, and these messengers may be intercepted or not delivered to the general’s voting results in the process of transmission, which will ultimately affect the unity of the army.

When the above story is mapped into a computer system, the general becomes a computer, and the messenger becomes a communication system. Some people think that this problem can be solved by encryption or signature, but essentially the encryption process, signature algorithm will also be wrong. Although encryption and signature can solve this problem to a certain extent, this problem is not to discuss the strength of these encryption signatures, but more to study the cluster system has objectively error, how to make the system work normally in the case of error.

Classic simple solution

First of all, why is this title a classic simple solution? Because this solution is only a simple solution, in many scenarios of modern systems, there is no universal solution ability.

After looking at the example above, one idea might spring up: after receiving votes from the same general, they would swap their results to see if the general was a traitor. For example, general A sends the attack instruction to General B and the evacuation instruction to General C, then General BC can exchange the instruction from General A and know that General A is A traitor, and then hunt him out and kill him, and no longer listen to his instructions.

But that doesn’t solve the problem at all. Although you can know there is A traitor after BC exchanges instructions, in fact, you can’t be sure that A is A traitor, because BC may make A “mistake” in the process of exchanging instructions, so the above idea cannot solve the problem.

Going back to the problem, we need to make the system work even when there are bugs, so we just need to design a system that is compatible with these traitors. How to understand? Going back to the Byzantine army, the Byzantine army needs at least 6 generals to take a city, so equip the army with more generals, say 10, to know how many traitors there are after verifying the message with a pair of interactive commands. As long as the number of loyal generals is greater than or equal to 6, the order can be carried out (attack or withdraw), otherwise the army stays put. The fault tolerance rate can be set according to your system and was described as 1/3 when this scheme was proposed.

It is also stated at the beginning that this scheme does not have universal problem solving capability in modern systems. One is the thousands of nodes of distributed ledger like Bitcoin. If you need to verify information in pairs, the process and cost is very large and will become impractical. In addition, not all systems of this nature can allow the execution of error nodes, such as registries, trading centers, etc.

Advanced solution – Proof of work for Bitcoin

After the “simple solution” scheme was proposed, many scheme algorithms were proposed, such as practical Byzantine fault tolerance (PBFT), Federal Byzantine Protocol (FBA), Authorized Byzantine fault tolerance Algorithm (dBFT) and so on. Because of the complexity and the length of the article, not a tautology, interested in online access.

But one Of the more interesting things is that “Proof Of Work, POW” is used in Bitcoin.

Workload proof is an economic response to service and resource abuse, or denial of service attacks. In general, users are required to perform some complex calculations that take appropriate time, and the answers can be quickly checked by the service side. The time, equipment and energy consumed are taken as the guarantee cost to ensure that the services and resources are used by the real demand. (Explanation from Wikipedia)

According to the scenario of Bitcoin, users need to obtain bitcoin through mining, which requires a large amount of computing resources. This mining process is actually a decryption algorithm designed by Bitcoin. The user (node) needs a certain amount of calculation to get the answer, and then check the calculation for the node. After success, the user will finally get the bitcoin reward for the right to keep accounts. In a nutshell, proof of work does not validate your process, only your results, but there are barriers to obtaining those results. And then we’ll talk about the principle of the algorithm and we’ll talk about the application of the consensus algorithm in a new space.

So how can bitcoin be counterfeited? In fact, it is still a majority vote in essence. After obtaining the results, other nodes need to verify voting. If you have more than 50% fake nodes, you can indeed tamper with data and control transactions. But proof of work has been introduced to make the cost of constructing a node sufficiently large that, with tens of thousands of nodes wanting to construct more than 50% of the false nodes, it is estimated that anyone with the financial resources to do so can already rule the earth.

The Byzantine general error may seem like a very serious problem with disastrous consequences, but in most cases it doesn’t happen. The next article will focus on more application-level consensus algorithms and discuss how the mainstream distributed middleware on the market can solve distributed consensus problems without considering “fault”.

For more technical articles, please pay attention to personal blog: Zackku.com public number: Zack said code