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?