The Paxos consensus algorithm is one of the earliest and most influential distributed consensus protocols, proposed by Computer Scientist Leslie Lamport in 1998. It was designed to help a group of computers agree on a single value, even if some of them crash or messages get delayed.

Free Link: Here

Table of Contents:

1. The Paxos Consensus Algorithm
2. Why Paxos Exists
3. The Three Roles in Paxos
4. The Problem of Agreement
5. Phase 1: Prepare / Promise
6. Phase 2: Accept / Accepted
7. Why Paxos Is Safe (Mathematical Proof)
8. Handling Failures in Paxos
9. Multi-Paxos: From One Value to a Log
10. Minimal Implementation (Pseudo-Go)
11. A Quick Summary

If you’ve gone through the earlier parts of this series, especially Raft, you’ll notice Paxos tackles the same goal: achieving consistency among distributed nodes. It many ways it was the predecessor to Raft. But unlike Raft, which was built to be intuitive and practical, Paxos is abstract, mathematical, and often difficult to reason about but underpins our understanding of consensus. Tricky to understand, yet fundamental.

Why Paxos Exists

Imagine we have a cluster of servers that need to agree on a single value — say, the next log entry, configuration version, or leader identity. Some nodes may fail, some may be slow, but we still want every non-faulty node to end up with the same result.

This is the consensus problem in distributed systems.

Paxos guarantees two key properties:

1. Safety: Only one value is ever chosen, and every node eventually learns that value.
2. Liveness: As long as a majority of nodes are functioning and can communicate, the system will eventually reach consensus.

Lamport’s core idea was to break the process into roles and phases that ensure agreement even in the face of failures.

The Three Roles in Paxos

Every node in Paxos can play one or more of the following conceptual roles:

1. Proposers — Nodes that propose a value to be chosen.
2. Acceptors — Nodes that decide which proposal to accept. They are the heart of Paxos.
3. Learners — Nodes that learn what value was finally chosen, so they can apply it (for example, to a log or a state machine).

In practice however, the same node can perform multiple roles. Many implementations merge them but for now I am separating them as it helps understand the algorithm easier.

The Problem of Agreement

Suppose we have five nodes: A, B, C, D, E.

We need at least a majority (3 nodes) to agree before any value is considered chosen.

They’re trying to agree on a single value for one “slot” or “instance” of consensus.
 That value could represent:

• A state machine command (like “set x=foo”)
• A new leader ID
• A database log entry

Let’s walk through the protocol in two phases: Prepare–Promise and Accept–Accepted.

Phase 1: Prepare / Promise

In Paxos, any node can be a proposer. There’s no built-in leader like in Raft. At any given time, one or more nodes might decide to propose a value.

Let’s assume A happens to be the one initiating the proposal for simplicity. Maybe it received a client request or just decided it’s time to propose a value.

A proposer wants to suggest a value (say, v = "bar") for acceptance.

1. It picks a unique proposal number n (e.g., 100) and sends a Prepare(n) message to all acceptors.
2. Each acceptor checks whether n is greater than any proposal it has seen before.

• If yes, it promises not to accept any proposals numbered less than n and replies with a Promise(n, n_prev, v_prev), where n_prev and v_prev are the highest proposal number and value it has already accepted.
• If no (meaning it already promised to a higher n), it ignores or rejects the message.

When the proposer gets a majority of promises, it moves to the next phase.

Phase 2: Accept / Accepted

1. The proposer examines all the promises it received.

• If any acceptor reported a previously accepted proposal, it must adopt the value with the highest n_prev.
• If none have accepted anything, it can stick with its own value.

2. It sends an AcceptRequest(n, v) message to the same quorum of acceptors.

3. Each acceptor accepts the request if it has not already promised to a higher n, records (n, v) as accepted, and replies Accepted(n, v).

Once a majority of acceptors accept (n, v), that value v is chosen, and learners are notified.

Notice that ‘E’ did not accept the message. So how does E catchup?

E can learn "X" through:

• A direct message from another node (proposer or learner),
• Or indirectly when future messages include the decided value.

So even if E didn’t accept "bar" itself, it learns that "bar" was decided by the majority and can update its local state accordingly.

Why Paxos Is Safe (Optional, mathematical proof)

The most important part here is that acceptors never break their promises, and proposers always inherit accepted values.

Even if multiple proposers race or some fail midway, only one value can satisfy a quorum of acceptors, because any new quorum will overlap with the previous one. This overlap ensures consistency across rounds.

Mathematically, quorums intersect, so no two different values can both be accepted by majorities.

A quorum (in this context) is any majority subset of the total acceptors.

If there are N acceptors:

• A quorum is any set Q such that |Q| > N / 2.

Example with 5 acceptors:
Possible majorities: {A, B, C}, {B, C, D}, {C, D, E}, etc.

Because each quorum is a strict majority, any two quorums must overlap in at least one acceptor.

Formally:

For any two quorums Q1 and Q2,
 Q1 ∩ Q2 ≠ ∅

Why?

If they didn’t intersect, their total size would be ≤ N (disjoint subsets).
But since both are > N/2, adding them gives > N. This is impossible!

Therefore, every quorum shares at least one common acceptor.

That overlap is the bridge of information between past and future rounds.

• Suppose quorum Q1 accepted (n1, v1) → value v1 is chosen.
• Any future proposer must gather promises from a new quorum Q2.
• Because Q1 ∩ Q2 ≠ ∅, at least one acceptor in Q2 was part of the quorum that accepted v1.
• That acceptor will report (n_prev = n1, v_prev = v1) when replying to the new prepare request.

The new proposer is obliged to carry forward that v1, ensuring that no different value can be proposed again.

This simple set-theoretic property of quorum intersection enforces global consistency without requiring global coordination. No second value can ever reach “chosen” state, because any majority decision must include at least one witness of the previous majority.

Handling Failures in Paxos

Proposer crashes:
If a proposer dies mid-way, another proposer can start a new round with a higher n. Since acceptors remember their highest promises, the system remains consistent.

Acceptor crashes:
As long as a majority survive, Paxos can still make progress.

Network partitions:
The majority partition can continue and decide on a value; minority partitions cannot progress but remain safe until they reconnect.

Multi-Paxos: From One Value to a Log

Basic Paxos agrees on one value. Real systems need to agree on many values like log entries in Raft. We cannot keep running this proposal every single time. It would be a waste of resources and time.

Multi-Paxos extends the algorithm by reusing the same leader (proposer) for multiple rounds, avoiding repeated prepare phases. Once a stable leader exists, consensus on subsequent entries is fast, similar to Raft’s AppendEntries.

We can think of Raft as “Multi-Paxos with a clear leadership and log structure.”

Minimal Implementation (Pseudo-Go)

This is a sketch of what the acceptor and proposer logic looks like:

// Acceptor
type Acceptor struct {
    promisedN int
    acceptedN int
    acceptedV string
}

func (a *Acceptor) OnPrepare(n int) (bool, int, string) {
    if n > a.promisedN {
        a.promisedN = n
        return true, a.acceptedN, a.acceptedV
    }
    return false, a.acceptedN, a.acceptedV
}
func (a *Acceptor) OnAcceptRequest(n int, v string) bool {
    if n >= a.promisedN {
        a.acceptedN, a.acceptedV = n, v
        return true
    }
    return false
}

// Proposer
func Propose(value string, acceptors []*Acceptor) string {
    n := GenerateProposalNumber()
    promises := collectPromises(n, acceptors)
    v := value
    if hasAccepted(promises) {
        v = highestAcceptedValue(promises)
    }
    accepts := sendAcceptRequests(n, v, acceptors)
    if majority(accepts) {
        return v // chosen value
    }
    return ""
}

A Quick Summary

Paxos is the classical consensus protocol ensuring safety and progress in unreliable networks. Even though Paxos only has two phases on paper, it’s harder to reason about and harder to implement correctly than Raft.

Raft explicitly defines leader election, which makes its flow predictable: all decisions go through one node. Paxos, on the other hand, allows any node to be a proposer. That means multiple proposers can start “Phase 1” concurrently, leading to overlapping proposal rounds and conflicts.

Paxos guarantees safety (no two nodes ever decide on different values) but doesn’t guarantee that consensus will finish. If proposers keep competing with each other, we can get livelock everyone keeps sending Prepare messages, but no one finishes. Raft solved this by introducing a deterministic leader that serializes proposals.

But understanding Paxos gives us the theoretical foundation behind almost every modern consensus engine.

We can think of Raft as a structured, engineer-friendly evolution of Paxos, optimized for real-world distributed systems.

In the next part we’ll look at another very popular consensus algorithm, also by Leslie Lamport called Byzantine Fault Tolerance.

See you there!