Documentation Index

Fetch the complete documentation index at: https://resources.devweekends.com/llms.txt

Use this file to discover all available pages before exploring further.

​

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):
    // An acceptor receiving a Prepare is being asked: "Will you promise
    // not to accept any proposal numbered less than n?" If the acceptor
    // hasn't made a higher promise already, it agrees and shares any
    // value it previously accepted -- this is how knowledge propagates
    // from earlier rounds to later ones.
    if n > promised_n:
        promised_n = n          // Record the promise (MUST be persisted to disk)
        reply Promise(n, accepted_n, accepted_v)
    else:
        reply Nack(promised_n)  // "I already promised someone with a higher number"

​

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):
    // The acceptor checks: "Is this proposal at least as high as anything
    // I've promised?" If yes, it accepts the value. The >= (not just >)
    // is important: the proposer that did the Prepare for n is now coming
    // back with Accept for the same n, which must succeed.
    if n >= promised_n:
        promised_n = n     // Update promise (MUST be persisted before replying)
        accepted_n = n     // Record acceptance (MUST be persisted before replying)
        accepted_v = v     // Record the accepted value
        reply Accepted(n, v)
    else:
        reply Nack(promised_n)  // "A higher-numbered proposal preempted you"

​

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

​

8.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.

​

8.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.

​

8.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.

​

8.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. This is Paxos’s most famous operational failure mode — it is safe (no wrong answer is ever chosen) but progress stalls indefinitely. Real-world example: early Google Chubby deployments saw this under high contention.
   • Fix: Use exponential backoff with jitter, or elect a stable leader (Multi-Paxos) so only one node proposes at a time.
2. Disk I/O: Acceptors must fsync their promised_n and accepted_n/v to stable storage before replying. If a node forgets its promise after a crash (e.g., data was only in the OS page cache), safety is violated — the node might accept a contradictory proposal. This is the kind of bug that only manifests under simultaneous power failure + leader crash, making it almost impossible to catch in testing.
   • Fix: Use fdatasync() or O_DIRECT writes. Profile your fsync latency — on cloud SSDs it is typically 0.1-1ms, but on spinning disks it can be 5-15ms, becoming your throughput bottleneck.
3. Unique Proposal Numbers: If two nodes use the same $n$ for different values, the protocol breaks. This is not a theoretical concern — it happens when nodes are provisioned from the same image with the same initial counter.
   • Fix: Always use (counter, server_id) pairs, where server_id is globally unique (e.g., from Zookeeper, or a MAC-based hash).
4. Confusing “chosen” with “known to be chosen”: A value is chosen when a quorum of acceptors has accepted it, but no single node may know this yet. The proposer infers it from the Accept responses, and learners must be told. A common implementation bug is to act on a value before confirming it is truly chosen — for example, applying a command to the state machine based on a single Accept response rather than waiting for a quorum. This violates safety because the value might not actually be chosen if other acceptors reject.
   • Fix: Only apply a value to the state machine after confirming a quorum of Accepted responses. Track this explicitly in your implementation.
5. Ignoring the “gaps” problem in Multi-Paxos: Unlike Raft, a Multi-Paxos log can have gaps — index 5 might be decided before index 3. If your state machine applies commands in order, you must wait for gaps to fill before applying later entries. Naive implementations that skip gaps or apply out of order produce inconsistent state.
   • Fix: Maintain an “applied up to” watermark and only advance it when all preceding entries are decided. Use no-ops to fill gaps proactively.

​

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.”

​

Interview Deep-Dive