Back to Blog

Tuesday, February 17, 2026

Paxos Made Simple: Understanding the Minimal Consensus Algorithm

Distributed SystemsBackend Development

Leslie Lamport's "Paxos Made Simple" demystifies one of the most fundamental algorithms in distributed systems. This paper argues that Paxos is not complex—it is the minimal algorithm required to solve consensus in an asynchronous, failure-prone network. This article breaks down the key concepts and insights from this foundational work.

1. Introduction — Why Paxos Exists

Lamport's goal is to demystify Paxos. The paper argues that Paxos is not complex—it is the minimal algorithm required to solve consensus in an asynchronous, failure-prone network.

Key framing:

  • Paxos is fundamentally a consensus algorithm
  • Replication and state machines come later
  • Complexity comes from weak assumptions, not poor design

2. The Consensus Algorithm

2.1 The Problem

Goal:

Processes propose values; exactly one value is chosen.

Safety requirements:

  • Only proposed values may be chosen
  • Only one value is chosen
  • No process learns a value was chosen unless it actually was

Model assumptions:

  • Processes may crash and restart
  • Messages may be delayed, lost, duplicated
  • No Byzantine failures
  • No timing guarantees

This is the strongest adversarial model Paxos must tolerate.

2.2 Choosing a Value — Why Paxos Needs Proposals, Numbers, and Promises

Initial idea: majority voting

  • If a majority accepts a value → chosen
  • But multiple values can split votes → no majority

Core insight

Acceptors must be allowed to:

  • accept multiple proposals
  • but ensure only one value can ever be chosen

This leads to proposal numbers.

Proposal numbers

Each proposal is: (number, value)

Properties:

  • Numbers are totally ordered
  • Higher number = later attempt

The key safety condition (P2)

If a value v is chosen, every higher-numbered chosen proposal must also have value v.

This prevents divergence.

Why promises are needed

If acceptors freely accept lower-numbered proposals:

  • old proposals can resurface
  • conflicting majorities become possible

So Paxos introduces promises.

Phase 1 — Prepare (Promise Phase)

A proposer:

  1. Chooses proposal number n
  2. Sends Prepare(n) to acceptors

An acceptor replies if n is higher than any it has seen:

  • promises not to accept proposals < n
  • returns the highest proposal it has already accepted (if any)

This:

  • locks out the past
  • forces future proposals to respect already-accepted values

Phase 2 — Accept

If a proposer receives promises from a majority:

  • it must propose:
    • the value from the highest-numbered accepted proposal, if any
    • otherwise, any value
  • It sends Accept(n, v).

Acceptors accept if they have not promised a higher number.

Why this works (core invariant)

Because:

  • majorities intersect
  • at least one acceptor remembers the chosen value
  • higher-numbered proposals must reuse it

→ only one value can ever be chosen

Optimization

Acceptors:

  • ignore prepares for lower numbers
  • remember only:
    • highest promised number
    • highest accepted proposal

This is the final Paxos algorithm.

2.3 Learning a Chosen Value

Once a proposal is accepted by a majority, it is chosen.

Learners can find out by:

  • acceptors notifying them
  • or querying acceptors later

Important:

  • Learning is separate from choosing.
  • A value may be chosen even if no learner knows yet
  • Learning is eventually consistent

2.4 Progress — Why Paxos Can Stall

Paxos guarantees safety, not liveness.

Problem:

  • Two proposers keep issuing higher-numbered proposals
  • They invalidate each other forever

Solution:

Elect a distinguished proposer (leader)

If:

  • the leader can talk to a majority
  • it uses increasing proposal numbers

→ progress is guaranteed

This does not affect safety.

2.5 Implementation Details

  • Proposal numbers must be unique
    • achieved by disjoint number ranges per proposer
  • Acceptors must use stable storage
    • promises and accepted proposals survive crashes
  • One process can play all roles

At this point, single-decree Paxos is complete.

3. Implementing a State Machine — Multi-Paxos

Now Paxos is applied repeatedly.

Replicated State Machine

  • Each command is a deterministic operation
  • All replicas must execute commands in the same order

Multi-Paxos

Run one Paxos instance per log slot

  • Slot i chooses command i
  • slot 1 → cmd1
  • slot 2 → cmd2
  • slot 3 → cmd3

Leader Optimization (Critical)

Once a leader is chosen:

  • Phase 1 is run once
  • Phase 2 is run for each slot

This turns Paxos into a practical replication protocol.

Gaps and No-ops

If slots are skipped (due to failure):

  • leader fills them with no-ops
  • preserves order

Key Result

In steady state:

  • each command costs one round of messages
  • Paxos is optimal under its assumptions

Final Conceptual Summary

This matters:

  • Paxos does not rely on message order. Paxos creates order through agreement.
  • Proposal numbers impose logical time
  • Promises prevent going backward
  • Majorities preserve decisions
  • Logs impose total order

Conclusion

Paxos represents the minimal algorithm for achieving consensus in asynchronous, failure-prone distributed systems. Its elegance lies in its simplicity: by using proposal numbers, promises, and majority intersections, Paxos ensures that only one value can ever be chosen while tolerating the strongest adversarial conditions. The extension to Multi-Paxos transforms this single-decree consensus into a practical replication protocol, forming the foundation for many modern distributed systems.