fast_paxos.md

Paxos

• Algorithm executes multiple rounds.
• An acceptor votes to accept atmost one value in a single round.
• Goal: Achieve consistency by ensuring that different values are not chosen in different rounds.
• Note that rounds can run concurrently, may be skipped altogether.

Accepter

State maintained by accepter:

# state maintained by acceptor
rnd[a]
vrand[a]
vval[a]

• rnd[a] - highest numbered round in which a participated, initially 0.
• vrand[a] - highest numbered round in which a has cast a vote, initially 0.
• vval[a]- The value a voted to accept in round vrand[a]; it's initial value is irrelevant. can be inferred using vrand[a] == 0

Constraint: vrand[a] <= rnd[a] is always true. Since it cannot vote without participating in it. But it can participate and doesn't vote.

Questions?

• what is this value that we are talking about?

Coordinator (role is often played by acceptors)

• For each round i, some coordiantor is pre-assigned to be the coordinator of round i.
• Moreover, each coordinator is assigned to be the coordinator for infinitely many rounds.
• Proposers send their proposals to coordinators.
• The coordinator picks a value in round i, that it tries to get chosen in that round.

State maintined by coordinator:

crnd[c]
cval[c]

• crnd[c] The highest-numbered round c has begun.
• cval[c] The value that c has picked for that round or the special value none if c has not yet picked a value for that round.

Questions?

• How do we decide coordinator for a given round i?

The Basic Algorithm

Phase 1a:

• Coordinator sends a message ( crnd, cval ) to each acceptor to participate in round i.

Phase 1b:

• Acceptor replies or ignores the message based on following conditions.

Success:
i > rnd[a]

Fail:
i <= rnd[a] (i.e., a has already begun round i or higher)

If success, it sends a message to coordinator containing (vrand[a], vval[a])

Phase 2a:

• Coordinator, on getting majority messages, sends acceptors a message to vote on value(cval, chosen by looking at the contents of Phase 1b message) in round i.

Phase 2b:

• Acceptor accepts the message to vote on v in round i based on following conditions.

Success:
i >= rnd[a] and vrnd[a] != i

Fail:
i < rnd[a] (accepted has started higher round)
vrand[a] == i (alreaded voted in this round and only one value can be accepted in this round)

Note: acceptor ignores the message no fail. On Accept, it sends a message to all learners announcing its round i vote.

Learner

• A learner accepts a value only if it receives message (Phase 2b) from majority of acceptors.

Important Constraint

• Coordinators are assigned unique rounds, which ensures that phase 2a messages cannot be sent for with different values in same round.