Multi-Paxos

The practical use of Paxos

Consensus algorithms are a valuable tool for creating fault-tolerant systems, but how consensus algorithms facilitate fault tolerance is often unclear. Let's try to make it clear in this lesson.

We know that the fundamental approach for achieving fault tolerance is through replication, which ensures that multiple copies of a system exist to mitigate the impact of any failures that may occur. Inconsistency among copies of a system is a common challenge that must be addressed to ensure the effectiveness of the replicated system. Inconsistency is introduced into the replicas when they execute the client requests (operations that change the system's state) in different orders. For all replicas to be consistent with each other, we need to maintain an order of operations that is the same across all replicas. When each replica executes the operations in the same order, they reach the same state. The consensus algorithm helps us establish the same order of operations across all replicas. That also means that all replicas will be in mutual agreement about the state of the system.

In this lesson, we will use the Paxos consensus algorithm as the basis to generate an order of operations that is the same across all system replicas, as shown in the following illustration. The order of the operations for each replica is persistently kept in each replica's log file called the operation log. It helps lagging replicas to catch up with the leading replicas.