Paxos Mental Model: Proposers, Acceptors, Ballots, Quorums, and Chosen Values

1. The problem: a later proposal must not erase an already chosen value

AtlasMart must choose one owner for a metadata slot. Proposer P1 tries ballot 10 with owner=east. If a majority of acceptors accepts that value, it is chosen. Later P2 may use a higher ballot 20, but higher ballot number does not mean “the new proposer can replace history.” Paxos safety requires P2 to discover and preserve a value that could already have been chosen.

A proposer attempts to get a value chosen. An acceptor persists promises and accepted proposals. A ballot/proposal number totally orders competing attempts. A learner discovers the chosen value; implementations may combine these roles on the same processes.

2. Phase 1: prepare and promise

P2 sends prepare(20). An acceptor that has not promised a higher ballot records that it will no longer accept proposals below 20 and replies with any proposal it previously accepted. The persistence of this promise is part of the crash-recovery model; forgetting it after restart can violate assumptions.

Once P2 receives promises from a quorum, it chooses the value from the highest-numbered accepted proposal in those replies. Only if none of the quorum reports a prior accepted value may P2 freely use its own desired value. This rule is the bridge that carries an earlier potentially chosen value into later ballots.

3. Phase 2: accept request and chosen value

P2 sends accept(20, value). An acceptor accepts if it has not promised a ballot greater than 20. A value becomes chosen once a majority accepts the same proposal. Because any two majorities intersect, a later successful phase-1 quorum intersects every earlier chosen majority. At least one intersecting acceptor can reveal the prior accepted value, and the proposer rule forces it forward.

4. AtlasMart lab: deliberately break the carry-forward rule

Ballot 10 first gets owner=east accepted by A/B/C, so it is chosen. A deliberately incorrect ballot-20 proposer asks C/D/E, learns that C accepted east, then ignores that fact and proposes west. That would create a second chosen value. The corrected Paxos path carries east forward.

acceptors = {name: {"promised": 0, "accepted_ballot": None, "accepted_value": None}
             for name in ["A", "B", "C", "D", "E"]}
majority = 3


def prepare(ballot, names):
    replies = []
    for name in names:
        a = acceptors[name]
        if ballot > a["promised"]:
            a["promised"] = ballot
            replies.append((name, a["accepted_ballot"], a["accepted_value"]))
    return replies


def accept(ballot, value, names):
    accepted = []
    for name in names:
        a = acceptors[name]
        if ballot >= a["promised"]:
            a["promised"] = ballot
            a["accepted_ballot"] = ballot
            a["accepted_value"] = value
            accepted.append(name)
    return accepted

print("BALLOT 10: VALUE EAST BECOMES CHOSEN")
r1 = prepare(10, ["A", "B", "C"])
a1 = accept(10, "owner=east", ["A", "B", "C"])
print("prepare promises:", r1)
print("accepted by:", a1, "chosen:", len(a1) >= majority)

print("\nBROKEN HIGHER BALLOT: IGNORE PRIOR ACCEPTED VALUE")
# Work on a copy to show the safety bug a non-Paxos proposer could create.
broken = {k: dict(v) for k, v in acceptors.items()}
for name in ["C", "D", "E"]:
    if 20 > broken[name]["promised"]:
        broken[name]["promised"] = 20
# C's promise contains owner=east, but the broken proposer ignores it.
wrong_accepts = []
for name in ["C", "D", "E"]:
    if 20 >= broken[name]["promised"]:
        broken[name]["accepted_ballot"] = 20
        broken[name]["accepted_value"] = "owner=west"
        wrong_accepts.append(name)
print("wrong ballot-20 accepts:", wrong_accepts, "=> owner=west would also be chosen")
print("safety violation if proposer ignores highest accepted value: TWO chosen values")

print("\nCORRECT BALLOT 20")
r2 = prepare(20, ["C", "D", "E"])
prior = [(b, v) for _, b, v in r2 if b is not None]
required = max(prior, key=lambda x: x[0])[1] if prior else "owner=west"
a2 = accept(20, required, ["C", "D", "E"])
print("promise replies:", r2)
print("highest accepted value carried forward:", required)
print("accepted by:", a2, "chosen:", len(a2) >= majority)
print("chosen values represented in acceptor state:", sorted({a["accepted_value"] for a in acceptors.values() if a["accepted_value"]}))
print("quorum intersection forces the later proposer to learn the prior chosen value")

5. Paxos is not “Raft without a leader”

Single-decree Paxos describes how to choose one value safely. Production systems usually need a sequence of slots and therefore use Multi-Paxos or related optimizations, often with a stable distinguished proposer/leader that amortizes phase 1. Raft bakes a stronger leader structure and log organization into the protocol to improve understandability. Both solve crash-fault consensus under specific assumptions, but their state machines and proofs should not be mixed casually.

6. Deliberately wrong approach: use “highest ballot wins” as last-write-wins

Ballot number orders protocol attempts, not business preference. If ballot 20 could simply choose a new value because 20 is greater than 10, Paxos would be a last-write-wins register rather than a consensus protocol. The prepare/promise history rule is what prevents a new proposer from silently replacing a value that may already be chosen.

7. Production judgment and bridge

Paxos-derived protocols are appropriate when the system needs one safe ordered decision stream and can accept majority/tail-latency costs. Monitor phase/ballot retries, rejected stale ballots, quorum response distribution, leader churn if using Multi-Paxos, durable-log latency, and stuck learners/replicas. Security still requires authenticated members and protected persistent state; classic Paxos is not Byzantine fault tolerant.

The next lesson turns consensus output into an externally useful correctness condition: linearizable metadata changes, leases, and fencing tokens. The important move is from “the group chose owner B” to “a paused old owner A cannot still mutate the protected resource.”

References

Foundational claims use primary research where practical. Product documentation is used only as a current implementation example and is not required for the mandatory labs.

• Lamport — Paxos Made Simple — Primary concise source for proposers, acceptors, proposal numbers, promises, accepted values, and quorum safety.
• Lamport — The Part-Time Parliament — Original Paxos publication with the deeper protocol formulation.
• Ongaro & Ousterhout — Raft paper — Useful comparison point; Raft states it produces an equivalent replicated-log result to Multi-Paxos while structuring the algorithm differently.
• Apache Cassandra — lightweight transactions / Paxos architecture — Current implementation example of Paxos-family conditional coordination; not required for this lab.