title: What is the proper behaviour for a Paxos agent in this scenario?
body: <p>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.</p>
  
  <p><img src="https://i96.photobucket.com/albums/l187/allen_a_george/StackOverflow/Strange_Paxos_Scenario.png" alt="alt text"></p>
  
  <p>A few points:</p>
  
  <ul>
  <li>Each agent acts as a proposer/acceptor/learner</li>
  <li>Prepare messages have form <code>(instance, proposal_num)</code></li>
  <li>Propose messages have form <code>(instance, proposal_num, proposal_val)</code></li>
  <li>Server1 and Server2 both decide to start the proposal process at the same time</li>
  <li>In the beginning messages M1, M2 and M3 occur simultaneously</li>
  </ul>
  
  <p>It seems here that although the protocol is 'correct', i.e. only one value <code>S2</code> is chosen, Server1 and Server2 believe that it was chosen because of different proposal numbers.</p>
  
  <p>Does the Paxos algorithm only terminate when the <code>Decide(...)</code> message is sent out to the learners? I must be misunderstanding <em>Paxos Made Simple</em> but I thought the choice was made the moment the proposers achieved quorum for their <code>Propose(...)</code> messages.</p>
  
  <p>If the choice is only made after the <code>Decide(...)</code> message is sent out to the agents, should Server2 terminate its sending of <code>Decide(1, 5, S2)</code> when it recovers because it saw a later <code>Prepare(1, 7)</code>?</p>