Demystifying Paxos: How Distributed Systems Achieve Consensus

Paxos Overview

Paxos is a message‑driven, highly fault‑tolerant consistency algorithm widely regarded as one of the most effective solutions for distributed consensus.

Originally proposed by Lamport, Paxos earned the 2013 Turing Award and has been adopted by many Google services (Chubby, Megastore, Spanner) as well as open‑source projects such as ZooKeeper and MySQL Group Replication.

Despite its strengths, Paxos is often criticized for being difficult to understand and complex to implement.

Background

In typical distributed systems, nodes may crash or experience network anomalies (delays, loss, duplication, reordering, partitions). Paxos must ensure that a single value is agreed upon despite these failures.

"The value can be a log entry, a command, or any application‑specific datum; its meaning depends on the context."

Key Concepts

Paxos defines three roles:

Proposer (proposal initiator)

Acceptor (voter)

Learner (observer)

A single process may play multiple roles simultaneously.

Proposals consist of a proposal number and a value ("Proposal = number + value").

Initial Analogy

The algorithm resembles a legislative process: a proposer submits a bill, acceptors vote, and learners learn the chosen bill.

Problem Statement

The system must guarantee safety: only proposed values can be chosen, at most one value is chosen, and any node that believes a value is chosen must be correct.

Derivation Process

Single Acceptor Attempt

With only one acceptor, the first proposal it accepts becomes chosen, but the system fails if that acceptor crashes, so multiple acceptors are required.

Multiple Acceptors

To ensure a single chosen value with many proposers and acceptors, Paxos introduces constraints:

P1: An acceptor must accept the first proposal it receives.

This leads to inconsistency when different acceptors accept different first proposals, so a majority rule is added:

A proposal is chosen only if a majority of acceptors accept it.

Proposals now carry both a number and a value, allowing later proposals to supersede earlier ones safely.

Proposer Algorithm

Before issuing a proposal, a proposer performs a Prepare phase: it selects a new proposal number N and asks a majority of acceptors to promise not to accept proposals numbered less than N and to report any previously accepted proposal with the highest number.

If a majority respond, the proposer adopts the highest‑numbered value returned (or chooses its own if none) and issues an Accept request for [N, V] to a (possibly different) majority of acceptors.

Acceptor Rules

An acceptor may ignore any request that would violate its promises. Specifically:

P1a: An acceptor that has already responded to a Prepare request with number > N may ignore a Prepare request numbered N.

Thus an acceptor only needs to remember the highest proposal number it has accepted and the highest Prepare number it has responded to.

Algorithm Phases

Phase 1 – Prepare: Proposer sends Prepare(N) to a majority; each acceptor replies with the highest accepted proposal (if any) and promises not to accept lower numbers.

Phase 2 – Accept: After receiving a majority of replies, the proposer sends Accept(N, V) where V is the value from the highest‑numbered reply (or its own). An acceptor accepts the proposal if it has not promised a higher number.

Learner Strategies

Three ways learners can learn the chosen value:

Every acceptor forwards accepted proposals to all learners (high communication cost).

Acceptors forward to a designated primary learner, which then notifies others (single‑point‑failure risk).

Acceptors forward to a learner group that disseminates the value (more reliable but complex).

Ensuring Liveness

By electing a distinguished “master” proposer that is the only one allowed to issue proposals, the system guarantees progress as long as the master and a majority of acceptors remain reachable.

Conclusion

The article detailed what Paxos is, its properties, the derivation of its safety and liveness constraints, the two‑phase protocol, and practical considerations, showing why Paxos remains a cornerstone of many modern distributed consistency algorithms.