Understanding Paxos by Just Answering Two Simple Questions

(Updated: )
CJ Sun, Caijun Sun, IOVI

To understand Paxos, first remember the following two stages of submission; and then answer the following two questions.

Paxos Interaction Process

The entire interaction process in Paxos cluster can be divided into two phases. There are three actors in Paxos cluster,

  • Proposer Proposer can make proposals (values or operation) to Acceptor.
  • Acceptor Acceptor can vote on the proposal made by the Proposer.
  • Learner The learner has no right to vote, only to learn from the Acceptor which proposal was selected.

Phase 1

  • Step A, Proposer

    • Prepare(N), N increase progressively and non-repeatable

  • Step B, Acceptor (MaxN, AcceptN, AcceptV)

    1. if (MaxN == null), return (pok, null, null)
    2. if (maxN > N), return none or error
    3. if (maxN < N), make maxN = N,
      1. if (AcceptN == null), return (pok, null, null)
      2. if (AcceptN != null), return (pok, AcceptN, AcceptV) // return previously accepted N and V; let the proposer of larger N to propogate AcceptV; AcceptV (AcceptN not included) must be set by the first proposer who gets (pok, null, null) more half of the quorum.

Phase 2

  • Step C, Proposer

    1. if pok > half quorum // once get pok > half quorum, don’t have to wait all the responses
      1. if all responses are (pok, null, null), send request (N, V) to acceptors, where V is a random value
      2. else get the acceptV of the max AcceptN among the responses (Technically, current Proposer’s N is not among them since it hasn’t sent the V yet), send request (N, acceptV_of_Max_AcceptN) to Acceptors; finally, go to Step E
    2. else, go back to Step A and start a new prepare request

  • Step D, Acceptor

    1. if (maxN > N), return none or error // maxN already updated by other proposers
    2. else, make AcceptN=N, AcceptV=V, return (aok, N, V) // meanwhile notify the Learners

  • Step E, Proposer

    1. if aok > half quorum, notify all Leaners the result
    2. else, go back to Step A and start a new prepare request

Two Questions

Answer following two questions, you will have a more deeper comprehension of how Paxos works. For simplicity, we assume the N will not change after Proposer fail to receive more than half of Acceptors’ acknowledgement. Otherwise, it may stuck in an endless loop if the Proposers compete intensively.

Question 1: Is it possible that after a period of time, more than half of Acceptors’ AcceptN will be empty?

Impossible, even there are fierce competition, within a certain period of time, the largest Proposer of N can finally write its value. It’s easy to understand that no Acceptor will reject its proposal since it got the largest N. Here we don’t need to consider what the final value AcceptN will be, just bear in mind that the largest Proposer of N will receive aok more than half of the quorum and a certain value will be written in this cluster.

Question 2: Here comes the most critical question. If ProposerX writes its value initially, can other Proposers (N is greater than the former) still tamper ProposerX’s value?

It may happen. Imaging that both Proposers N-1 and N start to propose meanwhile N-1 is a little bit ahead. N-1 firstly get more than half quorum and starts to send V-1. However, N may have changed the maxN on some Acceptors. In that case, N-1 will fail to write V-1 on these changed Acceptors even successfully write down V-1 on these Acceptors that haven’t be updated by Proposer N. In other words, Proposer N-1 can never get aok > half quorum. Meanwhile, Proposer N has already written its own V which will overwrite the values written by Proposer V-1.

Impossible, suppose ProposerX is the first one successfully writing down the value AcceptN. If ProposerY wants to write its own value, then it must meet two requirements. First, it must collect pok more than half of the quorum; Second, all the replies must be (pok, null, null). Since ProposerX has already written the value, then some of the pok received by ProposerY must be (pok, AcceptN, AcceptV), where AcceptN is submitted by ProposerX. Then ProposerY can only repeat the AcceptV and send it to Acceptors, we can imagine that the AcceptN can never be changed any more and only being repeatedly submitted.

BTW, as we declared at the beginning of this section that N will not grow for simplicity. However, we need to make N increase progressively when doing our own implementation. There are chances that we may run into the predicament that no Proposer can write the first value due to touch competition. It requires us design properly to avoid endless loop.

Summary

In summary, once a Proposer receives aok more than half of the quorum, then the final AcceptV in the cluster is determined. As for which Proposer’s V will be accepted, this is no longer important.

参考

  1. Paxos (computer science))