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)?