Paxos

Basic Paxos solves a single consensus instance: selecting at most one value from proposed values. Once a value is chosen, subsequent valid proposals cannot cause that instance to select a different value. To replicate a continuous command log, related instances can be run for different log slots, and protocol costs amortized under a stable leader.

The core of Paxos is not "the one with the most votes wins," but rather ensuring that new proposals preserve decisions that may have already been formed in the past as they proceed.

Roles and Terminology

A single server can assume multiple roles. Here we use a majority quorum from a fixed set, discussing a model that is non-Byzantine and allows crash recovery. The protocol requires acceptors to retain necessary persistent state after restart.

Why acceptors cannot simply accept the first value they see

If three acceptors first receive X, Y, and Z respectively, and never accept any further proposals, no value will achieve a majority. To make progress, acceptors must allow accepting subsequent proposals with higher numbers.

However, "allowing higher numbers to overwrite" introduces safety issues: A and B accept X, then B and C accept Y. Although the two majorities clearly intersect, two different values are selected. If the intersection node B lacks a constrained history inheritance rule, it might still participate in two different decisions.

Therefore, two complementary mechanisms are needed: use Promises to restrict old proposals accepted in the future, and use accepted records to constrain the values new proposers can propose.

Phase 1: Prepare and Promise

The Proposer selects a new unique ballot n and sends Prepare(n). A common construction is the lexicographical order of (local incrementing counter, proposer_id), and numbers already used cannot be reused after restart.

If an Acceptor allows promise n, it persistently records its promise lower bound and replies with a Promise: it will not accept proposals below this lower bound in the future, and attaches the highest-numbered proposal (accepted_ballot, accepted_value) accepted previously, or returns empty if none.

After receiving a majority of Promises, the Proposer examines these replies: if there are accepted records, it selects the value from the one with the largest accepted_ballot; if all are empty, it can choose its own new value. It is not arbitrary selection of any returned value, nor is it choosing the value that appears most frequently.

Phase 2: Accept and Accepted

The Proposer sends Accept(n,v). The Acceptor checks that it has not promised a higher ballot, persistently saves the accept record, and returns Accepted. If it has already promised a higher ballot, it rejects the old request.

When the same (n,v) is accepted by a majority, v is already chosen, even if the proposer crashes before collecting all responses. The Learner learning the decision is a separate event; "no one received a successful response" does not equal "no decision was formed."

Implementations usually advance the promise lower bound at the time of acceptance to the corresponding ballot and handle idempotent retries for messages with the same number. For the same instance, the same ballot cannot be used by a proposer to propose two different values.

A complete inheritance example

Assume X was accepted by A and B in ballot 4. A new proposer contacts B and C with ballot 7. B reports (4,X), C reports empty; the new proposer must therefore propose X. If the return contains a higher accepted_ballot, that value should be inherited; the inductive property of the protocol ensures it will not violate earlier chosen values either.

Conversely, if X in ballot 4 only reached A, and ballot 7 obtained empty Promises from B and C, Y can be chosen. B and C will no longer accept ballot 4, so the old proposer cannot make X achieve a majority anymore. This shows that Phase 1 not only collects the past but also constrains what can happen in the future through promises.

These examples illustrate two directions of safety: already chosen values cannot be swapped, and unchosen low-number competitors cannot bypass new majority promises to form conflicting decisions. For a complete derivation, see Paxos Made Simple.

Running two message traces: Chosen vs. Single-point Acceptance

Below, message delivery is written as sequential calls, and the two fields of the acceptor represent the state that should be persisted. Ballots are simplified to globally unique integers; Prepare with the same ballot can be replied to idempotently, and swapping values with the same ballot is explicitly rejected. The code does not implement networking, persistence, or fault recovery.

class Acceptor:
    def __init__(self):
        self.promised = -1
        self.accepted = None

    def prepare(self, ballot):
        if ballot < self.promised:
            return False, None
        self.promised = ballot
        return True, self.accepted

    def accept(self, ballot, value):
        if ballot < self.promised:
            return False
        if self.accepted and self.accepted[0] == ballot and self.accepted[1] != value:
            raise ValueError("Cannot change value for the same ballot")
        self.promised = ballot
        self.accepted = (ballot, value)
        return True

def phase1(cluster, names, ballot, proposed):
    replies = [cluster[name].prepare(ballot) for name in sorted(set(names))]
    promises = [accepted for ok, accepted in replies if ok]
    if len(promises) < len(cluster) // 2 + 1:
        raise RuntimeError("Did not obtain majority Promise")
    history = [accepted for accepted in promises if accepted is not None]
    return max(history, key=lambda accepted: accepted[0])[1] if history else proposed

# Trace 1: A, B already accepted X. Whether responses reach the proposer does not affect the fact that it is chosen.
c = {name: Acceptor() for name in "ABC"}
assert phase1(c, "AB", 4, "X") == "X"
assert c["A"].accept(4, "X") and c["B"].accept(4, "X")
assert sum(a.accepted == (4, "X") for a in c.values()) == 2
chosen_for_7 = phase1(c, "BC", 7, "Y")
assert chosen_for_7 == "X"
assert c["B"].accept(7, chosen_for_7) and c["C"].accept(7, chosen_for_7)
assert not c["B"].accept(4, "X")

# Trace 2: 4/X only reached A. B promised 4, but has no accepted record.
c = {name: Acceptor() for name in "ABC"}
assert phase1(c, "AB", 4, "X") == "X"
assert c["A"].accept(4, "X")
chosen_for_7 = phase1(c, "BC", 7, "Y")
assert chosen_for_7 == "Y"
assert c["B"].accept(7, "Y") and c["C"].accept(7, "Y")
assert not c["B"].accept(4, "X") and not c["C"].accept(4, "X")
assert c["A"].accepted == (4, "X")  # Local old accepted records can temporarily remain

In Trace 2, B replying to Promise(4) does not mean it accepted X. Phase 1 must return the accepted history; it cannot merge "the largest promised ballot" and "the largest accepted ballot/value" into a single field. The former restricts subsequent requests, while the latter constrains the values of new proposals.

Conversely, in Trace 1, B providing only a record of X is sufficient to constrain the new proposer; there is no need to vote again in B and C's replies to gather a "majority of replies saying X". B might be the only intersection between the new quorum and the old chosen quorum.

This model assumes the proposer complies with the selection returned by phase1, and globally a ballot is not assigned to two proposers. The acceptor's local same-ballot check can only detect conflicts it has seen, and cannot prevent a malicious proposer from lying to different acceptors about different values; Paxos's fault model is not a Byzantine model. State loss or illegal proposer behavior is not within the premises of this safety reasoning. Paxos Made Simple

Why can't new proposals arbitrarily change values?

Seeing only one X in the new Promise set might still require inheriting X: this reply might be the exact intersection with the old chosen majority. Below, we distinguish between two initial histories: "only A accepted" and "A, B already chosen," and retain the late request for old ballot 4. This allows us to see both how Phase 1 discovers the past and how it blocks future conflict paths through Promises.

Safety does not necessarily mean fast value selection

Two proposers might continuously increase ballots, interrupting each other, keeping the system safe but unable to complete for a long time. Therefore, implementations usually rely on a stable leader, backoff, or improved communication and scheduling conditions for eventual stability to make progress.

Simply retrying infinitely after receiving a rejection for a higher ballot does not guarantee low latency; it is necessary to avoid storming competition during fault recovery. When a majority of nodes are unreachable, the basic majority scheme cannot continue to select new values, but historical inheritance rules should not be abandoned because of this.

Multi-Paxos: Using Phase 1 results for multiple slots

Log slot and ballot are two dimensions: slot refers to the position of the command in the log, and ballot indicates who participates in the competition with which proposal generation. "New ballot" cannot be understood as "the next log entry."

After a stable leader establishes valid Phase 1 promises for relevant slots, it can execute Phase 2 for subsequent slots using the same ballot within the range covered by these promises, amortizing the Prepare cost. It is not because "I think I am still the leader" that recovery is arbitrarily skipped: the new leader must collect acceptance history, preserve constrained values slot by slot, and then handle missing slots.

Normally, each batch of proposals can use one round of accept requests and responses, but client communication, persistence, queues, and state machine application still exist. Multiple slots may reach decisions in parallel, but the state machine usually still needs to apply continuous prefixes; it cannot skip undetermined slot 11 to execute dependent commands just because slot 12 finished first.

Slot 12 being chosen first does not mean it can be executed first

Assume the initial state is 10, the command for slot 10 is add 2, slot 11 is subtract 1, and slot 12 is multiply by 3. 10 and 12 are known first, 11 is temporarily missing. The state machine can only execute 10 first, then stop at 11; otherwise, multiplying first then subtracting would yield the wrong 35, while the correct log order yields 33.

def apply_prefix(chosen, next_slot, value):
    while next_slot in chosen:
        value = chosen[next_slot](value)
        next_slot += 1
    return next_slot, value

chosen = {10: lambda x: x + 2, 12: lambda x: x * 3}
next_slot, value = apply_prefix(chosen, 10, 10)
assert (next_slot, value) == (11, 12)
chosen[11] = lambda x: x - 1
assert apply_prefix(chosen, next_slot, value) == (13, 33)
assert chosen[11](chosen[12](chosen[10](10))) == 35

"11 is unknown" does not mean "11 can be arbitrarily filled with no-op." The new leader still needs to collect the acceptance history for that slot through the recovery protocol, respecting constraints on potentially existing values; only when the protocol allows choosing a new value can a no-op be used to fill the empty slot. Log replication services need to record the set of chosen values and the applicable prefix separately; the known maximum slot cannot replace execution progress.

What is missing from algorithm to service

Production implementations also require log truncation and snapshots, membership changes, client request deduplication, flow control, read semantics, and operational recovery. These are not "Paxos does not allow," but rather the single-value protocol did not make unique engineering choices for the entire system.

Raft organizes election eligibility and log prefix constraints into a more explicit protocol structure; the implementation space for Multi-Paxos elections and log recovery is larger. Comparisons should focus on specific implementations and guarantees, rather than asserting that all replicas of a certain protocol always have exactly the same logs.

References

• Lamport: Paxos Made Simple.
• Consensus in Practice.

Keywords: Paxos, Multi-Paxos, ballot, prepare, promise, accept, accepted, chosen, quorum