Skip to main content

Consensus and Paxos in Distributed Systems

Before discussing Consensus and Paxos, we need to know some basic information. So, do you know that we use various distributed systems in day-to-day life even without knowing it? Let me give you an example. You probably have to use google docs, google slides, or any similar kind of cloud service. So if you think about google docs, can it be a single application executed on a single machine? You need to know that real-time processing and concurrent processing are very expensive for performance. Therefore, definitely, it should be a supercomputer or something that can handle those expensive computations in an efficient and effective way. In reality, it is a network of a large number of connected machines and devices. A distributed system is a system that has multiple components located on different machines that communicate and coordinate actions in order to appear as “a single coherent system” to the end-user. Consensus addresses a fundamental problem in the distributed system and Paxo

Consensus and Paxos in Distributed Systems


Before discussing Consensus and Paxos, we need to know some basic information. So, do you know that we use various distributed systems in day-to-day life even without knowing it? Let me give you an example. You probably have to use google docs, google slides, or any similar kind of cloud service. So if you think about google docs, can it be a single application executed on a single machine? You need to know that real-time processing and concurrent processing are very expensive for performance. Therefore, definitely, it should be a supercomputer or something that can handle those expensive computations in an efficient and effective way. In reality, it is a network of a large number of connected machines and devices.

A distributed system is a system that has multiple components located on different machines that communicate and coordinate actions in order to appear as “a single coherent system” to the end-user. Consensus addresses a fundamental problem in the distributed system and Paxos is a family of algorithms that can solve the consensus problem efficiently.

The Consensus Problem

Let's move into the main topic. What the consensus is in distributed systems? So, now you know that a distributed system consists of a large network of machines. Just think about a group of people who gathered together to do a task but no one knows exactly what to do. (Means don't know what mini-task should do at what time)

It is no matter even the headcount of the group is so high if they cannot manage their tasks and capabilities, the primary task will not be succeeded. For managing and successfully doing the task, they need to agree on certain things.

This is the consensus problem in a very simple way. For producing accurate and successful outcomes, each component or device in a distributed system also needs to agree on certain things. 
  • How do they agree?
  • Do need to all of them agree or a sufficient amount?
  • How to maintain the accuracy of this agreement process if some components crash?
  • ...

Above, I mentioned some sub-problems that needed to be answered for resolving the consensus problem completely. However, there are many more problems and conditions that need to be addressed.

Consensus Problem Definition

Let's discuss this a little bit further. "Shared State" is a very special concept in distributed systems. It is what it says. A distributed ledger with multiple replicated data nodes is a good example of that. Maintaining replicated data nodes provides several advantages such as,
  1. Availability; even if one node goes down, other nodes will be able to access the data,
  2. Quick response times; the user can obtain data quickly by placing data nodes closer to the user,
  3. Scalability by enabling multiple users to access different nodes so that a single node does not cause bottlenecks.

A mechanism for maintaining consistency is essential to maintain this shared state, which is the copies of these shared states must be identical on all the data nodes. We called this mechanism "Consensus".

In more academic definition, we can describe the consensus problem as follows.

Assume a collection of processes that can propose values. A consensus algorithm ensures that a single one among the proposed values is chosen. If no value is proposed, then no value should be chosen. If a value has been chosen, then processes should be able to learn the chosen value.

From the research paper "Paxos made simple, 2001" by Leslie Lamport.

According to the paper, the safety requirements for consensus are,

  • The system may choose only a proposed value,
  • The system will choose only a single value, and
  • A process never learns that a value has been chosen unless it actually has been.
The ultimate goal of solving the consensus problem is to ensure that the system eventually chooses some proposed value and, if the system has chosen a value, then a process can eventually learn that value.

Key Concepts

When discussing the consensus problem, there are a few key concepts that we cannot avoid. They are very fundamental concepts related to distributed systems. Let's take a look at them.



Concept 01: Fault-Tolerance

You know in this world anything is not perfect. Distributed systems are also. Sometimes they work as expected and sometimes they fail to perform as they should. Due to a distributed system depending on a large number of devices/machines this kind of failure can heavily affect the execution of the system. So it should have a mechanism to overcome this issue. That mechanism is called "Fault-tolerance". Fault tolerance is the property of a system to continue operating correctly despite any failures. There are several types of fault-tolerant models such as Crash fault-tolerant(CFT) and Byzantine fault-tolerant (BFT).

Concept 02: Message Communication

Another very important concept in distributed systems is how they communicate. Generally, we assume perfect links or reliable links for designing consensus algorithms that guarantee the following properties.
  • Reliable delivery; if the system sent a message from one correct process to another then the system eventually delivers the message,
  • No duplication; the system delivers a message exactly once.

There are mainly two types of message communication in distributed systems.
  1. Synchronous: the communication is termed to be synchronous if there is a fixed upper bound on message transmission delays.
  2. Asynchronous: If there are, no bounds on message transmission delays then the communication is termed to be asynchronous. This does not imply that the messages would take longer to get delivered but just that the delays can be arbitrary.
However, practically, most of the network communications happen in an asynchronous way (Maybe all). We can't make a system to deal with asynchronous ways because there is no time-bound. We don't know the reply message will come in the next minute or next year. So, we need to make it synchronous or seem like synchronous. "Eventually Synchronous" model is a solution for that, where the network can be asynchronous from time to time but is eventually synchronous.

Concept 03: Role of Leader

Developers and designers implement distributed systems in various ways. Commonly, they used "State Machine Replication(SMR)" mechanisms for that. We can implement SMR in a leader-based way or leaderless way.
  • Leader-based: The most responsible tasks handle by the leader while the followers are only responsible for acknowledging the order proposed by the leader and executing requests. There are different approaches for implementing leader-based distributed systems such as using a single leader or multi-leaders. We will find about them in a future post.
  • Leaderless: Systems that can be processed without a designated leader falling into this category. They also can be implemented using a virtual leader.
If a system has a leader, there is a probability that a failing leader can produce a failure for the whole system process. And also, due to all the followers having to deal with the leader, there will be a network and processing traffic at the leader. This issue is called the "Bottleneck at the leader". Mainly leaderless approaches are introduced to overcome this bottleneck issue at the leader.

Concept 04: Determinism

Consensus algorithms can be divided into two subsets as randomized and non-randomized which is deterministic. We will go deeper about this in another post.

Paxos Algorithms

We use consensus algorithms to solve the consensus problem. Paxos is a family of consensus algorithms. As the above-mentioned conditions(concepts) various types of Paxos algorithms have been implemented. We call them "Paxos Variants". Here, I list some Paxos variants used in distributed systems. Every one of them has different usabilities and properties. We will get to know about each of them in future posts.
  • Basic Paxos (Simple Paxos)
  • Multi Paxos
  • Fast Paxos
  • Egalitarian Paxos
  • WPaxos
  • Pig Paxos
My objective for this post is to give you a better understanding and a good starting point to learn, think, and observe in distributed systems field. We have to cover lots of things. So let's meet in another post to learn them too. Thank you. Warmly welcome for comments and further discussions.

     

Comments