Are Paxos and Raft not consensus algorithms/protocols?

As a member of the Internet, we are often immersed in the atmosphere of "distribution" - words such as high availability, high reliability, and high performance are everywhere, and nouns such as CAP, BASE, 2PC, Paxos, and Raft are also easy to use. However, some words are gradually misused or ambiguous in our "not rigorous" communication. Today, let's talk briefly about the word "Consistency".

[[318778]]

Paxos, Raft, etc. are often mistakenly called "consistency algorithms". However, "consistency" and "consensus" are not the same concept. Paxos, Raft, etc. are actually consensus algorithms.

In 1998, Leslie Lamport published an article titled "The Part-Time Parliament"[1] in ACM Transactions on Computer Systems. This was the first time that the Paxos algorithm was publicly published. However, after the publication, many people still felt that the original article was too difficult to understand. Later, Lamport wrote another article titled "Paxos Made Simple"[2]. When we want to learn about Paxos, we can directly read this article.

Back to the topic, we search for the word "Consistency" in "Paxos Made Simple". As shown in the figure below, there are actually no matching results.

On the other hand, when we searched for the word "Consensus", many matches appeared.

In other words, the word Consistency is not mentioned in the entire Paxos paper, so where does the statement "Paxos is a consistency algorithm" come from?

Similarly, the Raft paper “In Search of an Understandable Consensus Algorithm (Extended Version)” [3] gives a clear definition of Raft at the beginning: Raft is a consensus algorithm.... Note that the word here is consensus, not consistency.

At this point, let's open the dictionary again. At first glance, the translations of Consistency and Consenus in the dictionary are similar, both meaning "consistency", but a closer look reveals that they are different: Consistency: consistency, Consensus: consensus, unanimous opinion.

From a professional perspective, what we usually call consistency in a distributed system refers to the consistency of multiple copies of the same data, such as strong consistency, sequential consistency, and eventual consistency, which are all used to describe the consistency in the copy problem. Consensus is different. Simply put, the consensus problem is a process of making multiple nodes reach the same state through a certain algorithm. Consistency emphasizes the result, while consensus emphasizes the process.

The book "Distributed Systems Concepts and Design" defines the consensus problem as follows: To reach consensus, each process pi is initially in the undecided state and proposes a value vi from the set D. The processes communicate with each other and exchange values. Then, each process sets the value of a decision variable di. In this case, it enters the decided state. In this state, it no longer changes di.

The following figure shows three processes participating in a consensus algorithm. Two processes propose to "continue", and the third process proposes to "give up" but then crashes. The two correct processes both decide to "continue". (Where i = 1, 2, ..., N; j = 1, 2, ..., N.)

The consensus algorithm requires that the following conditions be met in each execution:

• Termination: Every correct process eventually sets its decision variable.
• Agreement: The decision value of all correct processes is the same, that is, if pi and pj are correct and have entered the decision state, then di = dj.
• Completeness: If correct processes all propose the same value, then any correct process in the decision state has chosen that value.

In the consensus problem, all nodes must eventually reach a consensus. Since the ultimate goal is for all nodes to reach a consensus, there is no distinction between strong and weak consistency. Therefore, when we see similar statements such as "Paxos is a strong consistency algorithm" and "Raft is a strong consistency protocol", we should look at the following content with a "critical" eye.

In most of our work, the difference between consistency and consensus is actually insignificant. But if we want to raise a dimension and study the content of the distributed field in depth, then if these most basic concepts are not clearly distinguished, it will greatly hinder the subsequent learning process.

The closer the words are, the more they should be clearly distinguished. Even the same word can have different meanings. For example, the C in CAP and ACID both stand for Consistency, but their meanings in their respective scenarios are different.

• The "C" in ACID refers to the consistency in transactions, which ensures the correctness of data in a series of data modification operations. That is, data will not disappear or increase out of thin air in multiple operations during a transaction, and each addition, deletion, and modification of data is causally related. For example, if user A transfers 200 yuan to user B, it will not happen that user A deducts the money but user B does not receive it.
• In a distributed environment, replication between multiple services is asynchronous and takes time, and will not be completed instantly. After the data of a service node is modified, there is a certain time interval before it is synchronized to other service nodes. If there are concurrent read requests during this interval, and these requests are load balanced to multiple nodes, inconsistent data from multiple nodes may occur because the request may fall on a node that has not completed data synchronization. The C in CAP is to ensure that the data read in a distributed environment is consistent.

In general, the C in ACID emphasizes the need to ensure data integrity and correctness during single database transaction operations, while the C in the CAP theory emphasizes the read and write consistency of multiple backups of a data.

Do you have anything to say about today’s knowledge points? Feel free to leave your thoughts in the comment section.

References http://lamport.azurewebsites.net/pubs/lamport-paxos.pdf

http://lamport.azurewebsites.net/pubs/paxos-simple.pdf

https://raft.github.io/raft.pdf

A brief discussion on CAP and Paxos consensus algorithms

The misused word “consistency”

Distributed Consensus: Viewstamped Replication, Raft, and Paxos