​

Paxos Consensus Deep Dive

​

1. Problem Restatement: Single-Value Consensus

• A set of processes (nodes), some of which may crash and recover
• A network that may lose, reorder, duplicate, or delay messages
• No bounds on message delay (pure asynchrony), so we cannot reliably distinguish slow vs dead

• Validity: v was proposed by some process
• Agreement: No two processes decide different values
• Termination: All non-faulty processes eventually decide (liveness – can be sacrificed under extreme asynchrony)

​

2. Roles and Quorums

​

2.1 Roles

• Proposers – suggest values to be chosen
• Acceptors – vote on proposals; a majority of them determines the chosen value
• Learners – learn the chosen value to apply it to state machines

​

2.2 Quorums

• With N acceptors, a quorum is any subset of size ⌊N/2⌋ + 1
• This ensures that any two majorities share at least one acceptor

​

3. Paxos in Two Phases

​

3.1 Proposal Numbers

• Simplest mental model: (counter, proposerId) pairs, ordered lexicographically
• Higher (counter, proposerId) means higher proposal number

​

3.2 Phase 1 – Prepare / Promise

• The proposer selects a new proposal number n and sends Prepare(n) to all (or a quorum of) acceptors
• Each acceptor maintains two pieces of persistent state:
  • promised_n – highest proposal number it has promised not to go below
  • (accepted_n, accepted_v) – highest-numbered proposal it has accepted so far (or ⊥ if none)

on Prepare(n):
    if n > promised_n:
        promised_n = n
        reply Promise(n, accepted_n, accepted_v)
    else:
        reply Nack(promised_n)

​

3.3 Phase 2 – Accept / Accepted

• The proposer chooses value v:
  • If any acceptor reported a previously accepted value (accepted_n, accepted_v) in its Promise, the proposer must choose the value with highest accepted_n among them
  • Otherwise, it can choose any value it wants (e.g., its own client request)

on Accept(n, v):
    if n >= promised_n:
        promised_n = n
        accepted_n = n
        accepted_v = v
        reply Accepted(n, v)
    else:
        reply Nack(promised_n)

​

4. Why This Works: Safety Intuition

Once a value v has been chosen, no other distinct value v' ≠ v can ever be chosen.

​

4.1 High-Level Proof Sketch

• Because both Q1 and Q2 are majorities, they must intersect at some acceptor a
• At the time v was chosen, a must have accepted (n, v)
• Later, when a receives Prepare(n'), it will respond with Promise(n', accepted_n = n, accepted_v = v)
• The proposer for n' must choose the accepted value with the highest accepted_n from Promises → that is v

​

5. Detailed Message Flow Example

​

5.1 No Contention Scenario

1. P chooses proposal number n = 1 and sends Prepare(1) to A1, A2, A3
2. All acceptors have promised_n = 0 and accepted_n = ⊥, so they all reply Promise(1, ⊥, ⊥)
3. P receives Promises from a quorum (any 2, say A1, A2)
4. Since none of them had an accepted value, P can choose its own value v = 42
5. P sends Accept(1, 42) to A1, A2, A3
6. Each acceptor checks n >= promised_n (true) and updates accepted_n=1, accepted_v=42, replying Accepted(1, 42)
7. P sees a quorum of Accepted and decides that value 42 is chosen

​

5.2 Competing Proposers Scenario

• P1 uses proposal numbers 1, 3, 5, …
• P2 uses proposal numbers 2, 4, 6, …

1. P1 sends Prepare(1) to all, gets Promises, moves to Phase 2
2. Before its Accept(1, v1) messages reach acceptors, P2 sends Prepare(2)
3. Acceptors respond Promise(2, accepted_n, accepted_v) depending on what they’ve already accepted
4. Because 2 > 1, they may promise to P2 even if they previously promised to P1

• Eventually, one proposer will “get ahead” with a higher proposal number and gather a quorum of Promises
• That proposer will then carry through with Phase 2 and choose a value consistent with any previously chosen value

​

6. Multi-Paxos: From One Value to a Replicated Log

​

6.1 The Cost of Naive Paxos

1. Latency: 2 round-trips (Prepare + Accept) per command.
2. Throughput: Heavy contention on acceptor state.

​

6.2 Multi-Paxos Optimization

• A leader runs Phase 1 (Prepare) for all future log indices simultaneously (conceptually).
• Once a proposer receives a quorum of Promises, it becomes the Master.
• For all subsequent commands, the Master skips Phase 1 and sends only Accept (Phase 2) messages.
• This reduces latency to 1 round-trip in the common case.

​

6.3 Master Leases

• Leases: Acceptors grant the Master a time-based lease (e.g., 5 seconds).
• While the lease is active, acceptors promise to reject any Prepare requests from other proposers.
• This allows the Master to perform local reads safely (Linearizable Reads), as it knows no other value can be chosen during the lease.

​

6.3.1 Advanced: Ephemeral Leases & Graceful Handoff

​

The Problem: The “Dead Leader” Gap

​

Optimization 1: Graceful Handoff

1. Step Down: The leader stops accepting new requests.
2. Synchronize: It ensures its log is fully replicated to a designated successor.
3. Renounce Lease: It sends a special message to acceptors saying, “I am renouncing my lease early.”
4. Instant Election: The successor can immediately run Phase 1 and take over without waiting for the timeout.

​

Optimization 2: Bidirectional Leases (Leader Sticks)

• If the Master is active and sending heartbeats/commands, the lease is automatically extended.
• This prevents the “Leader Duel” where a leader’s lease expires just as it’s trying to commit a value.

​

6.4 Log Compaction & Snapshots

1. Capture State: The state machine (e.g., a Key-Value store) captures its current state at index $i$.
2. Discard Log: All log entries from $1$ to $i$ can be safely deleted.
3. Bootstrap: A new node starts by downloading the snapshot and then only replaying the log from $i+1$ onwards.
4. Coordination: In Paxos, snapshots are usually managed locally by each node, but they must coordinate to ensure they don’t delete entries that a lagging peer might still need.

​

7. Mencius: High-Throughput Multi-Leader Paxos

​

7.1 How Mencius Works

• If there are $N$ nodes, Node $i$ is the “default leader” for all indices $k$ where $k \equiv i \pmod N$.
• Efficiency: Since each node is the leader for its own slots, it can skip Phase 1 (Prepare) and go straight to Phase 2 (Accept).
• Latency: No need to forward requests to a remote leader; nodes process local requests in their assigned slots.

​

7.2 Handling Idle Nodes (The Skip Mechanism)

• Node 1 must propose “No-Op” (Skip) for its slots so the cluster can move past them.
• If Node 1 is down, other nodes can run Paxos on Node 1’s slots to “force-skip” them.
• Trade-off: Mencius is extremely fast when all nodes are active, but performance degrades if some nodes are idle or slow, as they block the “common log” from progressing.

​

8. Advanced Paxos Variants

​

7.1 Fast Paxos (Low Latency)

• Classic Quorum: $Q = \lfloor N/2 \rfloor + 1$
• Fast Quorum: $Q_f = \lceil 3N/4 \rceil$
• If a client gets a “Fast Quorum” of identical responses, the value is chosen in one round-trip from the client’s perspective.
• Trade-off: If there is contention (multiple clients), it “collides” and falls back to a slower recovery path.

​

7.2 Flexible Paxos (FPaxos)

• You can have a small Accept quorum (e.g., 2 nodes out of 10) for fast writes.
• This requires a large Prepare quorum (e.g., 9 nodes out of 10) for leader changes.
• This is powerful for systems where leader changes are rare but writes are frequent.

​

7.3 EPaxos (Egalitarian Paxos)

• Any node can propose a command for any index.
• It uses dependency tracking (like Vector Clocks) to order concurrent commands.
• If two commands don’t interfere (e.g., different keys), they can be committed in 1 round-trip without a central leader.
• If they interfere, they use a “slow path” (2 round-trips) to resolve dependencies.

​

7.4 Dynamic Quorum Reconfiguration

​

1. The Naive Approach (The Trap)

• If some nodes use $N=3$ (Quorum=2) and others use $N=5$ (Quorum=3), you can reach a state where two different values are chosen because the quorums don’t overlap correctly across the transition.

​

2. The Paxos-in-Paxos Approach (Alpha)

• Current Membership $C_1$ is used for all indices up to $i$.
• Index $i$ contains a special command: RECONFIG(C_2).
• Once RECONFIG(C_2) is chosen at index $i$, all indices $> i + \Delta$ use membership $C_2$.
• $\Delta$ (the “alpha” parameter) is a pipeline limit. It ensures that the system doesn’t switch to $C_2$ while commands using $C_1$ are still in flight.

​

3. Joint Consensus (Raft Style)

1. The leader proposes the new configuration.
2. The system enters a state where both the old and new quorums must grant their approval.
3. Once the new configuration is committed, the old nodes can be safely decommissioned.

​

9. Paxos vs Raft: The Engineering Reality

• You need extreme performance or geo-distribution (EPaxos).
• You are building a system where “gaps” in the log are acceptable (e.g., non-deterministic state machines).
• You want to optimize quorum sizes (Flexible Paxos).

​

10. Formal Verification: Why Paxos is “Correct”

• TLA+: Leslie Lamport (creator of Paxos) also created TLA+, a formal specification language.
• Invariants:
  • P1: An acceptor must accept the first proposal it receives.
  • P2: If a proposal with value $v$ is chosen, then every higher-numbered proposal that is chosen has value $v$.
• Proving P2 is the core of Paxos’s safety. It relies on the induction over proposal numbers and the intersection of majorities.

​

11. Implementation Pitfalls

1. Livelock (The Duel): Two proposers keep preempting each other with higher proposal numbers.
   • Fix: Use exponential backoff or a stable leader (Multi-Paxos).
2. Disk I/O: Acceptors must fsync their promised_n and accepted_n/v before replying. If a node forgets its promise after a crash, safety is lost.
3. Unique Proposal Numbers: If two nodes use the same $n$ for different values, the protocol breaks. Always use (counter, server_id).

​

12. Interview “Master” Answer

“Paxos is a consensus protocol that ensures safety through quorum intersection. In its basic form, it uses a two-phase process: Prepare, where a proposer reserves a number and learns history, and Accept, where it proposes a value. Multi-Paxos optimizes this by electing a stable leader who skips the Prepare phase for subsequent commands. For high-performance needs, variants like Fast Paxos reduce latency by allowing direct client-to-acceptor communication, while EPaxos provides a leaderless approach to avoid bottlenecks. The core trade-off in Paxos is always prioritizing consistency over availability in the face of partitions, guaranteed by the fact that any two majorities must overlap on at least one node that ‘remembers’ the chosen value.”