Fast Paxos
November 11, 2014
- 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:
- 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.
- 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.
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.
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.
Picking a value in phase 2a
CP: For any round i and j with j < i, if a value v has been chosen or might yet be chosen in round j, then no acceptor can vote for any value except v in round i.
- paper doesn’t discuss leader election (coordinator)