Paxos Made Simple, in plain English

Reading Leslie Lamport’s Paxos made simple paper and an attempt at making it simpler

Before getting into this, I want to preface this blog by saying that the original paper Paxos Made Simple is a very well written introduction to Paxos and is a relatively easy read. This blog aims to simplify the concepts even further and explain how I would restate the ideas if I were explaining them to someone new to the topic.

The Problem

In a distributed system, multiple processes or nodes must agree on a common value, even when faced with challenges like network failures, crashes, and delays. Achieving consensus in such an environment is difficult because various issues can prevent nodes from reliably communicating or coordinating.

Paxos attempts to solve this problem by finding consensus among nodes under the following assumptions:

1. Asynchronous Communication: Nodes can experience network delays or failures, and they may not immediately be aware of these issues. Messages can be delayed or lost.
2. Fault Tolerance: Nodes may crash and restart, but they need to remember their state across failures. They must be able to recover and continue from where they left off.
3. Non-Byzantine Setup: Paxos assumes that nodes are not malicious. In other words, there are no Byzantine faults, meaning no nodes intentionally send incorrect or conflicting information.

These assumptions are common in a lot of distributed systems use cases which is what makes Paxos so popular.

Building up

A good place to start is the roles a node can play in our distributed system. Let’s say, we can have three types of roles for nodes in the system: proposers, acceptors, and learners.

1. Proposers are responsible for suggesting values to be agreed upon.
2. Acceptors are the nodes that decide whether to accept a proposed value.
3. Learners are simply informed of the outcome of the consensus, once a value has been chosen.

At first, it might seem logical to have a single acceptor that handles all the proposals. However, this creates a major problem: if that acceptor fails, no other proposals can be processed. To address this, Paxos requires a set of acceptors. But how many acceptors should we have?

A good solution is to require that a majority of acceptors accept a given value. This ensures that between two competing requests, the system can still reach consensus, since at least one node will detect conflicts and take appropriate action.

Since we have our acceptor count in place, we need to come up with a system for creating proposals. In order to ensure clarity and avoid confusion, each proposal needs to be identifiable. Therefore, every proposal is assigned a numerical ID, which should increase with each new proposal. The value associated with a proposal is considered “chosen” when its corresponding proposal ID is accepted by a majority of acceptors.

We assume for now that any node in the cluster can propose a value. But this creates a new problem, if any node can propose a value, a set of acceptor nodes might see two conflicting from two different proposers. Moreover, a proposer might not know the latest id and overwrite an earlier write that the system has agreed upon. To get around this, Paxos suggests a two step system:

Phase 1: Prepare Phase

• A proposer chooses a proposal ID (let’s call it n) and sends a prepare request with ID n to a majority of acceptors.
• When an acceptor receives a prepare request, it checks whether the proposal ID n is higher than any other proposal ID it has seen before. If it is, the acceptor sends a promise back to the proposer. The promise includes two things:

1. The acceptor promises not to accept any proposals with a lower ID than n.
2. The acceptor also returns the highest-numbered proposal it has already accepted, if any.

Phase 2: Accept Phase

• If the proposer receives responses from a majority of acceptors, it sends an accept request to the acceptors that responded to its prepare request.
• The accept request includes a value, which is typically the value associated with the highest-numbered proposal that the acceptors have already promised not to accept a lower ID than (as received in the first phase). This ensures that the value chosen is consistent across the system.
• When an acceptor receives an accept request, it will only accept the proposal if it has not already promised not to accept proposals with a lower ID. In other words, the acceptor will only accept a proposal if it hasn’t already committed to a proposal with a higher ID.

A proposer can abandon a proposal at any time, especially if it detects that another proposer has started a proposal with a higher ID. If an acceptor rejects a prepare or accept request because it has already seen a higher proposal ID, it will notify the proposer that it should cancel the proposal.

This ensures that the system always moves forward, with the most recent proposal being the one that eventually gets chosen by a majority.

An image showing the two phases of Paxos (src: https://www.the-paper-trail.org/post/2009-02-03-consensus-protocols-paxos/)

Progress

Imagine a scenario where two proposers keep proposing new proposal IDs without ever reaching consensus. For instance, Proposer A proposes ID n, and some acceptors agree. But then, Proposer B sends a proposal with ID n+1, which causes the accept requests from A to be rejected. A might then try to propose ID n+2, leading to a similar conflict.

To prevent this, Paxos uses a leader election process. If a “distinguished” proposer (a leader) uses a proposal ID greater than any that have already been proposed, it will succeed in having its proposal accepted, even if other proposers are active. The leader election mechanism ensures that the system progresses even in the presence of multiple proposers.

Once a majority of acceptors have accepted a proposal, it’s committed to their local stores. However, sending this information to a single learner would create a bottleneck. Instead, the information is sent to learners, to ensure that all nodes are informed of the consensus.

Finally, there’s one more potential issue: two proposers might select the same proposal ID n but propose different values. This could lead to confusion if acceptors agree to a proposal based on ID n but end up accepting different values. To avoid this, proposers typically choose their proposal values from disjoint sets. This ensures that two proposers won’t conflict by proposing the same proposal ID with different values.

Conclusion

This blog is my attempt to further simplify the Paxos Made Simple paper by Leslie Lamport. While this is just a high-level overview, I recommend reading the original paper — it’s an excellent resource for understanding the Paxos algorithm in more detail. Lamport’s paper does an outstanding job of breaking down the concepts and making Paxos accessible to a wide audience.

As with any other blog, I welcome feedback on how this could be better or what I may have gotten wrong here!

Sources:

1. https://lamport.azurewebsites.net/pubs/paxos-simple.pdf