title: Contradiction in Lamport's Paxos made simple paper
body: <blockquote>
    <p>Phase 2. (a) If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to each of those acceptors for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.</p>
  </blockquote>
  
  <p>As mentioned in the paper,</p>
  
  <blockquote>
    <p>A proposer issues a proposal by sending, to some set of acceptors, a request that the proposal be accepted. (<strong><em>This need not be the same set of acceptors that responded to the initial requests</em></strong>.)"</p>
  </blockquote>
  
  <p>But as my understanding, if we change Phase 2. (a) to:</p>
  
  <blockquote>
    <p>If the proposer receives a response to its prepare requests (numbered n) from a majority of acceptors, then it sends an accept request to <strong><em>an arbitrary set of majority acceptors</em></strong> for a proposal numbered n with a value v, where v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals.</p>
  </blockquote>
  
  <p>the algorithm will fail, following is an example. Consider that there are totally 3 acceptors ABC. We will use X(n:v,m) to denote the status of acceptor X: proposal n:v is the largest numbered proposal accepted by X where n is the proposal number and v is the value of the proposal, and m is the number of the largest numbered prepare request that X has ever responded.</p>
  
  <ol>
  <li>P1 sends 'prepare 1' to AB</li>
  <li>Both AB respond P1 with a promise to not to accept any request numbered smaller than 1. Now the status is: A(-:-,1) B(-:-,1) C(-:-,-)</li>
  <li>P1 receives the responses, then gets stuck and runs very slowly</li>
  <li>P2 sends 'prepare 100' to AB</li>
  <li>Both AB respond P2 with a promise to not to accept any request numbered smaller than 100. Now the status is: A(-:-,100) B(-:-,100) C(-:-,-)</li>
  <li>P2 receives the responses, chooses a value b and sends 'accept 100:b' to BC</li>
  <li>BC receive and accept the accept request, the status is: A(-:-,100) B(100:b,100) C(100:b,-). Note that proposal 100:b has been chosen.</li>
  <li>P1 resumes, chooses value a and sends 'accept 1:a' to BC</li>
  <li>B doesn't accept it, but C accepts it because C has never promise anything. Status is: A(-:-,100) B(100:b,100) C(1:a,-). The chosen proposal is abandon, Paxos fails.</li>
  </ol>
  
  <p>Did I miss anything here? Thanks.</p>