What is the proper behaviour for a Paxos agent in this scenario?

Question

I'm looking into Paxos and I'm confused about how the algorithm should behave in this contrived example. I hope the diagram below explains the scenario.

A few points:

• Each agent acts as a proposer/acceptor/learner
• Prepare messages have form (instance, proposal_num)
• Propose messages have form (instance, proposal_num, proposal_val)
• Server1 and Server2 both decide to start the proposal process at the same time
• In the beginning messages M1, M2 and M3 occur simultaneously

It seems here that although the protocol is 'correct', i.e. only one value S2 is chosen, Server1 and Server2 believe that it was chosen because of different proposal numbers.

Does the Paxos algorithm only terminate when the Decide(...) message is sent out to the learners? I must be misunderstanding Paxos Made Simple but I thought the choice was made the moment the proposers achieved quorum for their Propose(...) messages.

If the choice is only made after the Decide(...) message is sent out to the agents, should Server2 terminate its sending of Decide(1, 5, S2) when it recovers because it saw a later Prepare(1, 7)?

Answer 1

Just gonna redefine the terms (let's also throw out the 1 because we're only examining one Paxos iteration):

1) Propose(n) == propose(n), message from a proposer with current identity n

2) AcceptPrepare(n,v) == ack(n,v), message sent to proposer n. v is blank if this node hasn't accepted any value yet, o.w. v equals the value it has accepted

3) CreateDecide(n,v) == accept!(x,v), asking the nodes to accept this value from proposer with identity x. nodes will reject the message if they've ack'ed a prepare(n) message where n > x

Once quorum is achieved for prepare(n) -- that is, a majority have ack'ed the message -- then the proposer with identity n sends out a command accept!(n,v). If a prepare(n+x), x > 0, was sent out by a proposer with identity n+x -- and it's ack'ed by a majority -- between the ack(n,v) messages and the accept!(n,v), then a majority has promised not to accept values proposed with a timestamp < n+x, x > 0 (AKA the nodes will reject the accept!(n,v))

The choice is made as soon as a majority receives an accept!(n,v) message which they have not promised to ignore.

Thus, when server2 comes back online and it sends accept!(5,S2), it will be ignored because 5 < 7.