Basic Paxos: Prepare, Promise, Accept

Roles and ballots

Lamport's Paxos decides a single value among unreliable nodes. There are three roles, often played by the same processes: proposers suggest values, acceptors vote, and learners find out what was chosen. Every proposal carries a unique, increasing ballot number (also called a proposal number), for example (counter, node_id) so two proposers never pick the same one. A value is chosen once a majority of acceptors have accepted it in the same ballot. Acceptors keep two pieces of durable state: the highest ballot they have promised and the ballot and value they last accepted. A proposer needs two round trips: first it reserves a ballot with a majority, then it asks that majority to accept a value. The clever bit is in phase 1, where acceptors report what they have already accepted, which constrains what the proposer is allowed to propose.

The two phases of Paxos

A proposer sends Prepare(n), acceptors reply with Promise and any previously accepted value, the proposer sends Accept(n, v), and a majority of Accepted replies means v is chosen.

The two phases step by step

Phase 1a (Prepare): the proposer picks ballot n and sends Prepare(n) to acceptors. Phase 1b (Promise): an acceptor that has not promised a higher ballot promises to ignore anything lower than n, and replies with the highest-ballot value it has already accepted, if any. Phase 2a (Accept): once the proposer has promises from a majority, it chooses its value: if any promise reported an accepted value, it must use the one with the highest ballot; only if none did may it propose its own. It then sends Accept(n, v). Phase 2b (Accepted): an acceptor accepts unless it has since promised a higher ballot, and informs learners. When a majority accept in ballot n, v is chosen. If the proposer is rejected at any step, it retries with a higher ballot.

A minimal acceptor

Three acceptors in memory. After X is accepted by a majority in ballot 1, a second proposer with ballot 2 learns about X in its promises and is forced to propose X.

class Acceptor:
    def __init__(self):
        self.promised = -1        # highest ballot promised
        self.accepted = None      # (ballot, value) or None

    def prepare(self, ballot):                       # phase 1a -> 1b
        if ballot > self.promised:
            self.promised = ballot
            return ("promise", self.accepted)
        return ("reject", None)

    def accept(self, ballot, value):                 # phase 2a -> 2b
        if ballot >= self.promised:
            self.promised = ballot
            self.accepted = (ballot, value)
            return "accepted"
        return "reject"

acceptors = [Acceptor() for _ in range(3)]
print([a.prepare(1) for a in acceptors])
print([a.accept(1, "X") for a in acceptors[:2]])     # majority accepts X
replies = [a.prepare(2) for a in acceptors]          # a new proposer arrives
prior = [acc for kind, acc in replies if kind == "promise" and acc]
value = max(prior)[1] if prior else "Y"              # must adopt highest prior value
print("proposer 2 must propose:", value)

Output:

[('promise', None), ('promise', None), ('promise', None)]
['accepted', 'accepted']
proposer 2 must propose: X

त्वरित जाँच: In phase 2a, a proposer's promises report accepted values (ballot 3, 'A') and (ballot 5, 'B'). What must it propose?

• Its own new value
• 'A', because it was accepted first
• 'B', the value with the highest accepted ballot
• Nothing; it must restart phase 1