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)