1. The ideal goal of a distributed system

• The distributed system to which the blockchain belongs is also known as the "Replicated State Machine". Its goal is simple: all computers in the system agree on a certain output value, which means: all computers in the system Nodes/computers all have the same initial state, and after executing a transaction, all nodes have the same final state.

• This is not difficult to achieve if the computers are all functioning well and the communication between them is perfectly synchronized. But the reality is not the case. There are mainly two types of problems:

Some/some computer is down, it may not be able to calculate results, or it may not be able to connect to the system.

These problems are common and unavoidable, and once a problem occurs, it is impossible for all computers to agree on a certain output result. The famous distributed system "FLP Impossibility Principle" is described as follows: In a system with a reliable network but a minimal asynchronous model that allows node failures, there is no deterministic consensus algorithm that can solve the consistency problem. In layman's terms: as long as one computer in the system fails, the system cannot reach a consensus on the output value.

The FLP Impossibility Principle tells us: don’t waste time designing consensus algorithms for distributed systems that face all scenarios, that’s impossible.

secondary title

2. Consensus Algorithms for Distributed Systems

Although the impossibility principle of FLP is cruel, the benefits that distributed systems can bring are worth facing the difficulties. Since there is no consensus algorithm for all scenarios, it may be possible to find some consensus algorithms that are effective in specific scenarios. A consensus algorithm refers to a method for a distributed system to reach a consensus.

Let's see how scientists limit the scenario step by step and realize the consensus algorithm in this scenario.

First, if each computer in the system can come up with its own result, the situation is undoubtedly complicated, because we don't even know which result to reach a consensus on. Therefore, the first step in solving the consensus problem is to determine what the consensus is. The simplest method is that a certain computer has the final say, it proposes a result, and other computers agree with the result.

The computer that has the final say is called the proposer or leader. Although achieving consensus through the leader is not the only way to solve the problem, most protocols are implemented on this basis, including the consensus algorithm used in the blockchain system.

So you see, there is no absolute decentralization. The first step to achieve consensus is to determine a center.

• Digression: When we know this, we can establish a more effective discussion about decentralization. For example, here we can not talk about decentralization in general, but: whether the method of selecting this leader should go to centralized.

• Back to topic. The working steps of the consensus algorithm that requires a leader are roughly as follows:

• elect a leader;

• The leader proposes an outcome;

If everyone reaches a consensus on the result, the system outputs the final result; if everyone does not reach a consensus, go back to step 1 and start again.

This line of thinking provides a way to achieve consensus, but it is far from actually achieving consensus. Because if a computer can't connect to the system, it can't vote whether it agrees with the leader's result; if the computer with the problem happens to be the leader, the situation will be even worse, and the entire system will go to a standstill.

secondary title

3. Synchronization Hypothesis Consensus Algorithm

How to solve the above downtime problem? The method is simple to say: if a computer cannot connect to the system, ignore it and not participate in this round of consensus.

Then a new question arises, how do we know if it cannot connect to the system, or if it is participating in the consensus but the speed is slower than other machines?

As a result, scientists have developed one of the most important assumptions for solving the consensus problem: the synchronicity assumption. The synchronicity assumption introduces the concept of "timeout", which means that a time frame is set in advance, and if the leader fails to issue a proposal within the time frame, it will be eliminated and a new leader will be elected. In this way, failure of the leader node can be tolerated. (Note: synchronicity assumption is not equal to synchronicity assumption)

Both the Paxos algorithm and the Raft algorithm are proposed based on the assumption of synchronicity. But these two algorithms also need to make another assumption about the system, that is, that all computers in the system are "good guys", they either respond correctly to the leader's proposal, or fail to respond due to failure.

So, we finally have a distributed system that can achieve consensus, although it has strict conditions.

The Paxos consensus algorithm is a message-based and highly fault-tolerant consensus algorithm proposed by Leslie Lamport in 1990. It has an important position in the field of distributed system applications, including Google This algorithm is used in large distributed systems of many companies, including . And our first stage of exploration can also end here, followed by the second stage.

secondary title

4. Get rid of the "bad guys" in the system

Although Paxos can achieve consensus, its algorithm is based on the premise that all computers are "good guys". Consensus is enough. And if there are "bad guys" in the computer, the voice of the bad guy and the voice of the good guy will appear in the system, and the Paxos algorithm cannot handle this situation.

We need an algorithm that can achieve consensus even in the presence of bad actors, is it possible? Leslie Lambert developed a model to discuss this possibility, called the Byzantine Generals Problem, in which Byzantine nodes are bad guy nodes that transmit disruptive messages that prevent the entire system from reaching consensus.

In the paper "The Byzantine Generals Problem", Lambert proposed several solutions, one of which can achieve the consensus of the system when the Byzantine nodes are less than 1/3. In other words, if the number of bad guys in the system is less than 1/3, consensus can be achieved through algorithms.

• The DLS algorithm and PBFT algorithm (Practical Byzantine Fault Tolerant Algorithm) that appeared after that were all developed on this basis.

• PBFT is a representative Byzantine fault-tolerant algorithm, and its implementation process is roughly as follows. It doesn't matter if you don't understand the process, as long as you know that you can reach a consensus through this communication method.

• pre-prepare phase: the leader sends the result to all followers. The leader is node 0 in this graph, and it sends the results to followers 1, 2, and 3.

• Prepare phase: If the follower thinks the result is correct, tell all other nodes to approve the result. For example, node 1 will send its approval message to nodes 0, 2, and 3.

Commit phase: If the follower finds that more than 2/3 of the nodes agree with the leader's result, they will tell all other nodes to accept this result as the final result.

So far, we have solved the consensus problem of distributed systems with Byzantine nodes. However, if the number of bad guys in the system is equal to or more than 1/3, it is still impossible to reach a consensus. What we can do is to make the bad guys less than 1/3 through the system's access conditions or incentives.

The exploration of the second stage of the distributed system ends here, and then enters the third stage.

secondary title

5. Nakamoto Consensus Algorithm

Both Paxos and PBFT use the synchronicity assumption. In fact, almost all research on consensus algorithms is in this direction until the emergence of the Nakamoto consensus. Nakamoto consensus uses a non-deterministic mechanism.

What does it mean? We can think of a distributed system consisting of 12 computers as a jury of 12 jurors. We locked these 12 people in the conference room, handed in a note to explain the case, and then sat at the door of the conference room and waited for them to give the results of the trial.

These 12 people will have different opinions on how to judge, and may change their positions as the discussion progresses, and some people may fall asleep and be unable to express their opinions (refer to "Twelve Angry Men"). Then the person sitting at the door waiting has two options. The first option is for you to discuss it, and I can wait as long as you want, but in the end you must give me the only definite trial result; the second option is that I can’t wait, and you first give the result that most people agree to. Me, if there is a result that more people agree with, I will change to that result.

Obviously, we can only choose one of the two. If the result is required to be confirmed, there is no guarantee that the result will be obtained; if the result is required, there is no guarantee that the result must be the final result.

• This is the case with distributed systems. There are only two options. The first option is called Finality, which means "certainty of results" or security; the second option is called Liveness, which means the activity or availability of the network.

• These two choices determine two different design ideas for distributed consensus:

The pursuit of Finality is the priority result, so it is necessary to make requirements on the network. PBFT and Tendermint are both algorithms of this type. They follow the assumption of network synchronization, and systems using such algorithms will not fork.

As an aside, choosing one of Finality and Liveness is also a manifestation of the CAP theorem (impossible triangle) of distributed systems. The theorem says: For a distributed system, it is impossible to satisfy consistency, availability, and partition tolerance at the same time. Because partition fault tolerance means that the system must be able to tolerate network partitions, and the real network will definitely be partitioned, so this condition must be met. In fact, the CAP theorem says that it is impossible for a distributed system to satisfy both consistency and Availability, among them, CAP consistency reflects Finality, and CAP availability reflects Liveness.

Whether it is the FLP Impossibility Principle or the CAP Impossibility Theorem, they are not telling us: this road is difficult to walk through, and if you make a breakthrough, it will be a great innovation; what they tell us is: this road will not work, you have to What to do is to make trade-offs and choices according to needs.

Consensus algorithms using synchronicity assumptions have been introduced in detail above, and they achieve consensus by introducing the concept of timeouts and ignoring computers that have problems.

Nakamoto consensus using a non-deterministic mechanism is also simple to describe: if you see a proposed block with the most proof-of-work, accept that block, also known as the longest chain rule. Its specific implementation process is familiar to everyone, so I won't repeat it in this article.

Now, let's see how systems that use synchronicity assumptions (Finality, used more in PoS) differ from systems that use non-deterministic mechanisms (Liveness, used more in PoW). But it needs to be reminded that not all PoS are Finality routes, such as Casper FFG; and PoW is not limited to the Liveness route, although no one has designed the Finality consensus on PoW.

The difference between PoW and PoS is that one is Work and the other is Stake. The reason why this point needs to be emphasized is that in discussions about PoW and PoS, we are often not discussing the difference between the Work mechanism and the Stake mechanism, but comparing the difference between the Finality system and the Liveness system. For example, "permission-free" is basically a topic between the Finality system and the Liveness system, not the debate between Work and Stake.

Let's go back to the room with 12 reviewers. In order to pursue Finality, each reviewer needs to know everyone else's ideas, and also needs to tell everyone else their ideas, so the communication complexity will increase rapidly with the increase of the number of reviewers, and the whole system will therefore Not available, so the number of jurors must be controlled.

Then for a distributed system, only a few nodes are selected to enter the meeting room, and they decide the consensus, while other nodes only accept the consensus. Therefore, there are three roles in this system, leader, follower and learner. The leader and follower are the reviewers in the conference room. They need to work well, otherwise the system may not be able to reach a consensus.

The Nakamoto Consensus pursues Liveness. Nodes/reviewers do not need to communicate with every other node, they only need to communicate with the nodes around them, so the communication complexity will not increase due to the increase in the number of nodes. If you want to be a judge, you can walk into the conference room and become a judge without permission, and it will not make it difficult for the jury to reach a consensus. At the same time, you can not work or leave at any time. There are only two roles in the system, the leader and the follower, and everyone participates in the consensus in that conference room.

It seems that the Nakamoto consensus seems to be more in line with everyone's expectations for the openness of distributed systems, but don't forget that it can be designed in this way because it sacrifices Finality, and its output is a probabilistic final result.

Just imagine, you get 100% a cup of coffee at Starbucks, but Starbucks does not receive 100% of the money, which is not in line with the rules of the world that most people understand. So the non-deterministic mechanism has its own shortcomings and unsuitable scenarios.

On the other hand, after the finality system guarantees the certainty of the results, the system design must in turn pursue Liveness; and after the Liveness system ensures the openness of the network, the system design must inversely pursue Finality. In order to improve the certainty or security of the result, Nakamoto Consensus needs to make other concessions, such as TPS.

So you see, designing a distributed system is like making a deal with Satan, you get some and you have to give some. There is no best system, only a system suitable for solving certain types of problems; there is no simple index comparison, only under what settings to achieve this index.

If you understand this, the purpose of this article has been achieved, and our exploration of distributed systems is all over here.

Six, go further

Lianwen Note:

- How Does Distributed Consensus Work?

https://medium.com/

This article was inspired by the article "How Does Distributed Consensus Work?" If you want to learn more about distributed systems, I recommend this article, which introduces distributed consensus from a professional perspective; also recommend "WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS", which systematically lists classic papers on distributed systems.

https://ethfans.org/

- WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS

http://alvaro-videla.com/

Lianwen Note:

- Chinese translation of "How Distributed Consensus Works", by EthFans

Another key problem in distributed systems is timing. All consensus algorithms need to solve it, but because it is another clue, this article does not cover it. If you want to know, you can learn from Dr. Leslie Lambert (how old are you): "Time, Clocks and the Ordering of Events in a Distributed System".

• If you are interested in finding a balance between Finality and Liveness, you can study the Casper FFG consensus, which has a part of Liveness and a part of Finality. At the same time, you will also find the difference between Casper FFG's PoS and Tendermint's PoS.

• Finally, make a summary of this article, which mainly includes the following contents:

• Two theorems: FLP impossibility principle; CAP impossibility theorem.

• Two types of fault tolerance: downtime fault tolerance; Byzantine fault tolerance.

• Two consensus algorithm design ideas: Finality; Liveness.

Three consensus algorithms: Paxos, PBFT, and Satoshi Nakamoto consensus.

References:

There will be inaccuracies and incompleteness caused by simplification and analogy in the article, please understand, thank you for correcting.

2.《WHAT WE TALK ABOUT WHEN WE TALK ABOUT DISTRIBUTED SYSTEMS》，Alvaro Videla

3.《Time, Clocks and the Ordering of Events in a Distributed System》，Leslie Lamport

4.《The Byzantine Generals Problem》，LESLIE LAMPORT、ROBERT SHOSTAK、MARSHALL PEASE

5.《Paxos Made Simple》，Leslie Lamport

6.《Bitcoin: A Peer-to-Peer Electronic Cash System》，Satoshi Nakamoto