Understanding Paxos by Just Answering Two Simple Questions

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(K), K increase progressively and non-repeatable
  • Step B, Acceptor (MaxN, AcceptN, AcceptV)

    1. if (MaxN == null), return (ok, null, null)
    2. if (maxN > K), return none or error
    3. if (maxN < K), make maxN = K,
      1. if (AcceptN == null), return (pok, null, null)
      2. if (AcceptN != null), return (pok, AcceptN, AcceptV)

Phase 2

  • Step C, Proposer

    1. if pok > half quorum,
      1. if all responses are (pok, null, null), send accept(K, V), where V is a random value
      2. else get the acceptV of the max AcceptN among the responses, send accept(K, acceptN_of_Max_AcceptN)
    2. else, go back to Step A and start a new prepare request
  • Step D, Acceptor

    1. if (maxN > K), return none or error
    2. else, approve and return aok, meanwhile make AcceptN=K, AcceptV=V, notify the Learners
  • Step E, Proposer

    1. if aok > half quorum, notify all leaners the result
    2. else, 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 K 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 K can finally write its value. It/s easy to understand that no Acceptor will reject it proposal since it got the largest K. Here we don’t need to consider what the final value will be, just bear in mind that the largest Proposer of K 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 (K is greater than the former) still tamper ProposerX’s value?

Impossible, suppose ProposerX is the first one successfully writing down the value. 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 value can never be changed any more and only being repeatedly submitted.

BTW, as we declared at the beginning of this section that K will not grow for simplicity. However, we need to make K 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))