Tracing Single-Decree Paxos Execution

The Essence of Consensus

Before diving into the algorithm, let's formalize what we're trying to achieve. A consensus algorithm must satisfy three properties:

1. Agreement (or Safety): All non-faulty nodes that decide on a value must decide on the same value.
2. Validity (or Integrity): If all nodes that propose a value propose the same value v, then any value that is decided must be v. More simply, the system can't just invent a value.
3. Termination (or Liveness): Every non-faulty node eventually decides on a value.

However, a famous result in distributed systems, the FLP Impossibility Proof, showed that it is impossible for a deterministic algorithm to guarantee all three properties in an asynchronous network where even a single node can crash. Paxos makes the pragmatic choice to guarantee agreement and validity at all costs, while sacrificing guaranteed termination. This means that in certain failure scenarios, Paxos may not make progress, but it will never produce an incorrect result.

Professor Lindsey Kuper gives an excellent overview of these properties and the FLP result in the following clip.

The Roles and the Stage

The Paxos algorithm defines three distinct logical roles. A single physical server can, and often does, play all three roles simultaneously.

• Proposers: These are active agents that initiate the consensus process by suggesting a value. A system can have multiple proposers active at once.
• Acceptors: These are the "voters" or the fault-tolerant memory of the system. They receive proposals and decide whether to accept them. Decisions are made when a majority of acceptors agree. This majority is often called a quorum.
• Learners: These are passive agents that simply find out what value has been chosen by the acceptors.

The guarantee that any two quorums (majorities) have at least one member in common is the mathematical foundation upon which Paxos's safety rests. For a set of $N$ acceptors, a quorum is any subset of size $\lfloor N/2\rfloor +1$.

A Simple Trace: The Happy Path

Let's trace a successful run of single-decree Paxos, where we want to agree on a single value. We will follow a two-phase protocol.

The article "Paxos: Lamport's Crown Jewel" provides a clear, step-by-step trace that mirrors this diagram.

Let's summarize the two phases from that "happy path" trace:

Phase 1: Prepare-Promise

1. Prepare: The Proposer chooses a globally unique and monotonically increasing proposal number n. It sends a Prepare(n) message to a majority of Acceptors. This number n is just an identifier for the round; it is not the value we are trying to agree on.
2. Promise: Each Acceptor receives the Prepare(n) message. If n is higher than any proposal number it has seen before, it records n and sends back a Promise(n) message. This promise means the Acceptor will not accept any future proposal with a number less than n.

When the Proposer receives Promise(n) from a majority of Acceptors, Phase 1 is complete. It has secured a "lease" for proposal number n.

Phase 2: Accept-Accepted

1. Accept: The Proposer sends an Accept(n, v) message to a majority of Acceptors. Here, v is the actual value it wants to propose (e.g., "foo" in the article's example).
2. Accepted: An Acceptor receives the Accept(n, v) message. As long as it hasn't made a conflicting promise to a higher proposal number in the meantime, it accepts the proposal, persists the value v, and replies with an Accepted(v) message to the Proposer and any Learners.

When a majority of Acceptors have accepted v, the value is considered chosen. Consensus has been reached.

Handling Conflict and Failures

The simple trace is straightforward, but the real power of Paxos is revealed when things go wrong. What if multiple Proposers are active at once? What if a Proposer fails after some Acceptors have accepted its value, but before a majority is reached?

This is where the protocol's subtle but critical rules come into play.

Scenario 1: Dueling Proposers

Imagine two proposers, P1 and P2, trying to get different values chosen simultaneously. P1 might start with Prepare(5), and P2 might start with Prepare(6).

As shown, a higher proposal number always wins the right to proceed. Acceptors will promise to ignore the lower-numbered proposal. This can lead to a state of livelock, where proposers continuously interrupt each other with higher numbers, and no value is ever chosen. This is the liveness failure that FLP predicted. In practice, systems solve this by using randomized backoffs and, more importantly, by electing a stable leader (which is the core idea of Multi-Paxos, our next topic).

Scenario 2: Recovering a Previously Accepted Value

This is the most critical scenario for understanding Paxos's safety guarantee. Let's see how Paxos prevents a previously accepted value from being lost or overwritten. This requires us to refine the rules for Phase 1 and 2.

The best way to understand this is to see how the "happy path" logic breaks and how the full Paxos algorithm fixes it. Professor Kuper's video explains this brilliantly by "filling in the asterisks" on the simple version of the algorithm.

Let's formalize the two crucial rule refinements you just saw:

1. Refined Promise Rule: When an Acceptor receives a Prepare(n) message, if it has already accepted a value v_prev with a proposal number n_prev, it must include both n_prev and v_prev in its Promise response to the Proposer. The response becomes Promise(n, n_prev, v_prev).

2. Refined Accept Rule: When a Proposer receives a majority of Promise responses, it examines all of them. If any of the responses included a previously accepted value, the Proposer must choose the value associated with the highest proposal number (n_prev) from all the responses. It then proposes that value in its Accept message, abandoning its own original value if necessary. If no responses contained a previously accepted value, it is free to propose its own.

This mechanism ensures that any value that has made progress towards being chosen is "picked up" and carried forward by subsequent proposals, guaranteeing it won't be lost.

To solidify this, let's trace this exact scenario using our text resource.

Conclusion

In this lesson, we have dissected the single-decree Paxos algorithm. You can now trace its execution in both ideal and failure-prone scenarios.

Here are the key takeaways:

• Paxos prioritizes safety over liveness, accepting that in cases of extreme contention (dueling proposers), the system may not make progress, but it will never reach an inconsistent state.
• The protocol operates in two phases: Prepare/Promise to reserve a proposal number and Accept/Accepted to agree on a value for that proposal.
• Consensus is reached when a quorum (a majority) of Acceptors accept the same value.
• The core safety mechanism lies in the refined rules: Acceptors report previously accepted values in their Promise messages, and Proposers are obligated to adopt the value from the highest-numbered previous proposal, ensuring that past decisions are never overwritten.

Single-decree Paxos is foundational, but running the full two-phase protocol for every single decision is inefficient. In our next lesson, we will explore Multi-Paxos, an optimization that introduces a stable leader to bypass the Prepare/Promise phase for subsequent decisions, making Paxos a practical and performant solution for building replicated logs and state machines.