Part 2: The consensus problem in Distributed Systems

The article is reposted from the personal blog: https://dhhoang.github.io/posts/consensus-problem-en

Examples of Distributed Systems developed and used in practice include Database system (SQL, NoSQL), Cache system (Redis, Memcached), Message-Queue system or Publish / Subscribe (Kafka, RabbitMQ … ). These systems have different features, but the core of them all has to solve a fundamental problem, the consensus problem .

As mentioned in Section 1 , one of the features of Distributed System is the ability to act as a unified entity for the user. To achieve this goal, during operation, the processes in the system need to reach consensus on the state of data (state) as well as the next operational steps (action). Since the processes may not reside on the same physical computer, they are required to communicate over the network to reach this consensus. However, both the computer and the network can experience problems, making it not easy to communicate to ensure consistency between processes.

The way to reach consensus among the processes in Distributed Systems, even when there is a problem, is called the Distributed Consensus problem. To better understand this problem, in this article we will discuss two illustrative examples.

Two generals problem

The problem is stated as follows: There are 2 generals commanding 2 armies stationed in different locations and facing an enemy army. These two generals need to come to a decision: attack the enemy together, or retreat together. If they attack the opponent together, they will win, if they withdraw, they will preserve their forces. On the contrary, if two generals make an opposite decision (1 attack, 1 retreat), they will be defeated by the opponent. The two generals can use the courier to send letters to each other, but each communication has the potential to be captured by the opponent, resulting in the mail being not shipped. So what protocol do the two generals above need to use to be able to come to unified action?

Before continuing the article, I encourage you to try to figure out how to solve this problem yourself. Basically, the problem required one of the two generals to propose an action and send a letter to the other general asking for consensus. However, how does the proposed general know that the information has reached the other general or not?

For those of you knowledgeable about the Computer Networking array, you may find that this problem has many similarities with the TCP / IP protocol, which is a network protocol developed to allow senders to be secure. that the information has reached the receiver. We can adopt a similar approach to this problem, based on the DATA / ACK protocol of TCP / IP. One general ( G1 ) will propose a plan and send information to the other ( G2 ). Upon receiving the letter, G2 will follow the proposed plan and send a confirmation letter (ACK) to G1 . If G1 receives a confirmation letter, G1 will do the same.

However, the above contact letters may all be lost along the way, according to the conditions of the problem. If letter G1->G2 is lost, G2 will not receive the offer. Even worse, if the ACK letter is lost, G2 will attack while G1 has yet to decide on the action. So how do we solve this case? The short answer here is, the problem does not have a perfect solution . Indeed, the opponent is theoretically capable of intercepting all communications between the two generals, and in that case there is no way to reach consensus.

The main meaning of the 2-general problem is to illustrate one thing, that is, there is no “perfect” solution to the consensus problem. However, we can come up with a more “realistic” approach, by assuming that the opponent can’t always catch all the communications sent between the two generals. Accordingly, it is possible for G1 resend the proposal if an ACK is not received after a certain time, until it receives an ACK from G2 (similar to TCP / IP’s retransmission mechanism).

Byzantine General’s problem

Abbreviated as BGP, this problem is stated as follows: There are n generals from Byzantine (name of a medieval empire located in present day Turkey and southeastern Europe), each of them commanding a team troops, surrounded by an enemy stronghold. They need to reach consensus on a plan of action: either attack ( A ), or retreat ( R ). Generals can communicate with each other by securely communicating (communication is not lost or swapped). However, some of these n generals were enemy spies, and had the ability to send out any message, to prevent the remaining armies from agreeing. The problem is: 1) find a protocol so that generals (not spies) can agree on the action ( A or R ), 2) find out if the number of spies affects How is the above protocol?

This problem was posed by the computer scientist Leslie Lamport in the article ” The Byzantine Generals Problem “, and the name of the “Byzantine” problem type (see section 1) is named after this problem. There are many people who confuse this problem with the 2 generals problem (2GP) mentioned in the previous section. The two problems have some differences. First, BGP has any number of troops (instead of just 2 like 2GP). Second, both generals in 2GP are “loyal”, while BGP has one or more generals who are spies. Third, in 2GP, the communication between the two armies could be interrupted, while in BGP we consider the communication between the generals to be perfect.

To come to the solution, let us try to start reasoning from a few simple cases. With n=1 , the problem becomes minimal, there is no consensus here. With n=2 , we have a relatively simple solution: one champion proposes option v and sends a letter to the other, and both will do v . Since the communication between the two generals is guaranteed, they will surely reach a consensus. In the event that one of the generals was a spy, any action by the other would be valid.

The problem becomes more complicated when n=3 . In the simplest case with m=0 spies, our solution is similar to the case n=2 . A General G1 will propose a plan of action v and send information to the remaining generals. The remaining generals when received word will follow v . So what if m=1 ? In this case, the sender ( G1 ) could be a spy and would send conflicting messages to the other two G2 ( G2 and G3 ). We can try using communication between G2 and G3 to confirm the information. Even so, if G1 was a spy, G2 and G3 would still receive inconsistent information about action plan v . Indeed, if G1 sends A to G2 and R to G3 , G2 and G3 will see the following information:

The same thing happens when G2 or G3 are spies. This leads to G2 or G3 unable to determine who the spy is, and unable to agree on a v . More generally, BGP has no solution for the case of n generals and m spies if 3m >=n .

In other words, BGP can only solve when the number of spies is less than 1/3 of the generals ( 3m < n ). The algorithm for solving this problem is called Byzantine Fault Tolerance (BFT). The details of the algorithm (and the proof) are relatively complex, so I will not present it here (encourage you to read this algorithm in Lamport’s article). However, I will summarize a few main points:

• The idea : Generals are divided into 2 roles: 1 general plays the role of commander ( C ), the others are deputy generals ( L ). Commanders will propose plans v and the deputy will follow. In order to meet the requirements of the problem even when Commander C is a spy, the deputy generals will inform each other about the plan v that they receive. For example, deputy L3 will send v3 (received from C ) to the remaining deputy generals. After this process is finished, each deputy L will get a vector of values ​​that the vice generals receive from the command: L = [v1 v2 ... v_(n-1)] , and will choose the price which value is the majority.
• However, the aforementioned L3 could be a spy and could send different v3 values ​​to the remaining vice generals. So how is this case resolved? If L3 is a spy then v3 is practically meaningless. The only important thing here is that the vice generals (not spies) agree on v3 . This consensus can be achieved by solving a “child” consensus problem, similar to the original problem, but removing C Instead, L3 now plays the commanding role, aiming to unify the v3 value among the remaining deputy generals. This is the recursive solution . Since this solution only makes sense when CC is a spy, the number of spies in this “sub” system is m-1 . This recursion is repeated m times for each deputy, until the case m=0 (which is the simple case discussed above).
• The performance of the solution : The complexity in terms of the amount of information to be sent of this solution is O(n^m) , as a result of the recursive process. This means that the above solution is not very practical in large systems with many processes (because the amount of information to send here increases exponentially). There have been many studies improving the solution to improve the performance of this problem, such as pBFT, Speculative Byzantine Fault Tolerance …

Practical application of BFT algorithm

The BFT algorithm (and variants) is intended to solve the consensus problem for systems that might experience a Byzantine problem type (see the definition of this type of problem again in Part 1 ). Examples of these systems include Blockchain, NASA or SpaceX aerospace systems …

However, in most practical Internet applications, this type of Byzantine failure rarely occurs (compared to other types of fail-stop, fail-recover). The reason is: 1) DS systems such as Database, Message Queue … are often deployed in a secure environment (usually in data centers with good control of network connectivity through walls. fire …), separate from individuals attempting to attack from outside; 2) the system’s connection to the external Internet environment is typically encrypted based on security protocols such as SSL. For example, when you read this blog with the link including ” https “, you are assured that the content of the blog is actually from the writer, not being swapped; 3) standardized protocols such as TCP / IP, HTTP … also help to protect the system from Byzantine errors caused by hardware malfunction.

That said, although the BFT algorithm is relatively complex and has low performance, we do not need to worry about applying this algorithm to our project. In the following sections, we will discuss more Consensus algorithms for systems that are considered “immune” to the Byzantine failure type.