# Basic Paxos: Prepare, Promise, Accept — Distributed Systems & Consensus (Raft / Paxos)

Source: https://www.skillbyai.com/en/distributed-consensus/dc-basic-paxos

> Walk through the two phases of single-decree Paxos and the roles of proposers, acceptors and learners.

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

![Four stages: prepare, promise, accept, and accepted by a majority.](assets/figures/distributed-consensus/section-5-map.svg) — Figure 5.1: Prepare(n) -> Promise -> Accept(n, v) -> Accepted (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.

```python
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
```

**Quiz:** 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
- [x] 'B', the value with the highest accepted ballot
- [ ] Nothing; it must restart phase 1

*Answer:* 'B', the value with the highest accepted ballot. The rule is to adopt the value with the highest accepted ballot among the promises. This preserves any value that might already be chosen.