In Paxos, can an Acceptor accept a different value after it has already accepted one?

Question

In Multi-Paxos algorithm, consider this message flow from the viewpoint of an acceptor:

receive: Prepare(N)

reply: Promise(N, null)

receive: Accept!(N, V1)

reply: Accepted(N, V1)

receive: Accept!(N+1, V2)

reply: ?

What should the acceptor's reaction be in this case, according to the protocol? Should it reply with Accepted(N+1, V2), or should it ignore the second Accept!?

I believe this case may happen in Multi-Paxos when a second proposer comes online and believes he is (and always was) leader, therefore he sends his Accept without Preparing. Or if his Prepare simply did not reach the acceptor. If this case may not happen, can you explain why?

Answer 1

I disagree with both other answers.

1. Multi-Paxos does not say that the Leader is the only proposer; this would cause the system to have a single point of failure. Even during network partitions the system may not be able to progress. Multi-Paxos is an optimization allowing a single node (the Leader) to skip some prepare phases. Other nodes, thinking the leader is dead, may attempt to continue the instance on her behalf, but must still use the full Basic-Paxos protocol.

2. Nacking the accept message violates the Paxos algorithm. An acceptor should accept all values unless it has promised to not accept it. (Ignoring is allowed but not recommended; it's just because dropped messages are allowed.)

3. There is also an elegant solution to this. The problem is with the Leader's round number (N+1 in the question).

Here are some assumptions:

• You have a scheme such that round ids are disjoint across all nodes (required by Paxos anyway).
• You have a way of determining which node is the Leader per Paxos instance (required by Multi-Paxos). The Leader is able to change from one Paxos instance to the next.
  Aside: The Part-time Parliament suggests this is done by the Leader winning a prior Paxos instance (Section 3.1) and points out she can stay Leader as long as she's alive or the richest (Section 3.3.1). I have an explicit ELECT_NEW_LEADER:<node> value that is proposed via Paxos.
• The Leader only skips the Prepare phase on the initial round per instance; and uses full Basic Paxos on subsequent rounds.

With these assumptions, solution is very simple. The Leader merely picks a really low round id for it's initial Accept phase. This id (which I'll call it INITIAL_ROUND_ID) can be anything as long as it is lower than all the nodes' round ids. Depending on your id-choosing scheme, either -1, 0, or Integer.MIN_VALUE will work.

It works because another node (I'll call him the Stewart) has to go through the full Paxos protocol to propose anything and his round id is always greater than INITIAL_ROUND_ID. There are two cases to consider: whether or not the Leader's Accept messages reached any of the nodes the Stewart's Prepare message did.

When the Leader's Accept phase has not reaches any nodes, the Stewart will get back no value in any Promise, and can proceed just like in regular Basic-Paxos.

And, when the Leader's Accept phase has reached a node, the Stewart will get back a value in a promise, which it uses to continue the algorithm, just like in Basic-Paxos.

In either case, because the Stewart's round id is greater than INITIAL_ROUND_ID, any slow Accept messages a node receives from the Leader will always result in a Nack.

There is no special logic on either the Acceptor or the Stewart. And minimal special logic on the Leader (Viz. pick a really low INITIAL_ROUND_ID).

---

Notice, if we change the OP's question by one character then the OP's self answer is correct: Nack.

• receive: Prepare(N)
• reply: Promise(N, null)
• receive: Accept!(N, V1)
• reply: Accepted(N, V1)
• receive: Accept!(N-1, V2)
• reply: Nack(N, V1)

But as it stands, his answer breaks the Paxos Algorithm; it should be Accept!

• receive: Prepare(N)
• reply: Promise(N, null)
• receive: Accept!(N, V1)
• reply: Accepted(N, V1)
• receive: Accept!(N+1, V2)
• reply: Accept!(N+1, V2)

Answer 2

The correctness of Multi-Paxos is conditioned on the requirement that the leader (i.e., proposer) does not change between successive Paxos instances. From The Part-Time Parliament Section 3.1 (The Protocol of the Multi-Decree Parliament):

Logically, the parliamentary protocol [a.k.a. Multi-Paxos] used a separate instance of the complete Synod protocol [a.k.a. Paxos] for each decree number. However, a single president [a.k.a. proposer/leader] was selected for all these instances, and he performed the first two steps of the protocol just once.
_{[Added emphasis is mine.]}

Therefore, Multi-Paxos makes the assumption that the case which you describe—when a second proposer comes online and believes he is (and always was) leader—will never happen. If such a case can happen, then one should not use Multi-Paxos. With respect to the second possibility—when the second proposer's Prepare did not reach the acceptor—the fact that the second proposer already sent out an Accept! means that it previously sent out a Prepare that was Promised by a quorum of acceptors. Since the acceptors already promised to the first proposer on round N, then the second proposer's Prepare must have been sent out prior to round N. Therefore, the final Accept!(N+1,V2) must have a counter less than N.

Edit: It should also be noted that this version of the protocol is not robust to Byzantine failure:

[The Paxon Parliament's protocol] does not tolerate arbitrary, malicious failures, nor does it guarantee bounded-time response.
_{—The Part-Time Parliament, Section 4.1}

Answer 3

Perhaps a simpler answer is to observe that this is the case when the Prepare(N+1) command was accepted by a majority that did not include the acceptor in question.

To elaborate: Once a leader knows that some majority has Promised(N+1), it then sends Accept(N+1,x) to all acceptors, and even if some other majority of acceptors reply with Accepted(N+1) then consensus has been reached.

This is not that unusual a scenario.

Answer 4

(Answering my own question.)

My current understanding is that I should not to accept the value in N+1 (i.e. not answer at all or send a NACK), thus forcing the leader to possibly start another round with Prepare (if the majority hasn't reached consensus yet). After I receive Prepare(N+2), I shall reply with Promise(N+2, V1) and continue as usual.