Paxos: Accepting Proposals With Different Values and Consensus in Paxos

Question

I have a number of questions about Paxos which I can't answer in full confidence from reading the paper (Paxos Made Simple).

My questions are loosely based around the following quote:

In Paxos, a value is chosen when a single proposal with that value has been accepted by a majority of the acceptors. However, we can allow for multiple proposals to be chosen, but we must guarantee that all chosen proposals have the same value.

The first property, P1, states:

P1: An acceptor must accept the first proposal that it receives.

Therefore, if we have an proposer, which sends an prepare(n) statement to a majority of acceptors, this majority can always respond to a prepare request, and because this is the first proposal, the majority must accept this proposal.

However, in the case where multiple proposals are proposed at about the same time, it can be possible that no single value is accepted by a majority. For this reason, it is necessary for an acceptor to be able to accept multiple proposals.

Question 1: This means that an acceptor can accept a proposal with a value v2 after it has accepted a proposal with value v1. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Now, if we look at P2B:

If a proposal with value v is chosen, then every higher-numbered proposal issued by any proposer has value v.

And then later:

If the proposer receives the requested responses from a majority of the acceptors, then it can issue a proposal with number n and value v, where v is the value of the highest-numbered proposal among the responses...

Question 2: Does this mean that if a proposer proposes a value, v1, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, v2? If they want to make a proposal, they must propose the same value, v1? The only way they could propose a different value would be to start a new instance of Paxos. The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

Question 3: Can an acceptor respond to a proposer with a promise if consensus has already been reached?

Question 4: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send an proposal, correct?

Answer 1

Question 1: This means that an acceptor can accept a proposal with a value $v_2$ after it has accepted a proposal with value $v_1$. Otherwise, I don't see how it can be guaranteed that a majority of acceptors accept proposals with the same value. Is this correct?

Yes, it is possible for an acceptor to accept a proposal with number $n_2$ and value $v_2$ after it has accepted a proposal with number $n_1$ and value $v_1$. Consider the following scenario where there are two proposers $p_1$ and $p_2$ and three acceptors $a_1, a_2,$ and $a_3$:

1. $p_1$ proposes $\texttt{propose}(n_1,*)$ to $a_1$ and $a_2$.
2. both $a_1$ and $a_2$ respond to $p_1$ with (a) a promise never again to accept a proposal numbered less than $n_1$ and (b) no proposal because they have not accepted any ones.
3. $p_1$ receives the two responses from $a_1$ and $a_2$. Now $p_1$ is free to select its own value $v_1$. $p_1$ sends $\texttt{accept}(n_1, v_1)$ to $a_1$ and $a_2$.
4. $a_1$ accepts $(n_1, v_1)$ but $a_2$ does not (maybe this message to it has been lost; note that an acceptor can ignore any request without compromising safety).
5. $p_2$ proposes $\texttt{propose}(n_2, *)$ to $a_2$ and $a_3$ ($n_2 > n_1$).
6. Because, in 4, $a_2$ does not accept $\texttt{accept}(n_1,v_1)$ from $p_1$, both $a_2$ and $a_3$ respond to $p_2$ with a promise never again to accept a proposal numbered less than $n_2$.
7. $p_2$ receives the two responses from $a_2$ and $a_3$ and is also free to select its own value $v_2$. $p_2$ sends $\texttt{accept}(n_2, v_2)$ to $a_1$ and $a_3$.
8. $a_1$ can now accept the proposal $(n_2, v_2)$ from $p_2$.

---

Question 2: (1) Does this mean that if a proposer proposes a value, $v_1$, that is accepted by a majority, it is now impossible for the same proposer, or another proposer, to propose another value, $v_2$? (2) If they want to make a proposal, they must propose the same value, $v_1$? (3) The only way they could propose a different value would be to start a new instance of Paxos. (4) The reason you would want to make a proposal with the same value as the chosen value is because the chosen value might not have been received by any of the learners. Is this correct?

For (1): yes; For (2), yes. The invariant $\texttt{P2B}$ in Paxos is the key to its correctness.

For (3): I think you have confused an instance of Paxos with a round in an instance of Paxos. They are two important concepts. We call a round the collection of all messages labeled with some particular proposal $n$. An instance of Paxos consists of multiple rounds, each round corresponding to a proposal with a different number. If you consider multiple instances of Paxos, please refer to Section 3 "Implementing a State Machine" in the paper. It is often called "multi-Paxos".

For (4): in page 6, it reads "A proposer can make multiple proposals, so long as it follows the algorithm for each one. It can abandon a proposal in the middle of the protocol at any time". That is to say, as a proposer, you are free to make multiple proposals as you want, for no matter what reasons. However, a major reason would be to learn the value already chosen: at phase 2(a), you will have to select the value chosen, if any.

---

Question 3: Can an acceptor respond to a proposer with a promise if consensus has already been reached?

Yes, it does no harm. Again, the invariant $\texttt{P2B}$ works.

---

Question 4: The promises guarantee that a majority of acceptors will always accept a value, because the proposer must receive a promise from the majority of the acceptors before it can send a proposal, correct?

Are you discussing about the correctness of Paxos? Are you regarding the "promise mechanism" as the key to success? If so, you are almost right: however, it is hard to identify a single factor in Paxos. If it must be done, once again, it is the $\texttt{P2B}$ invariant.