title: What to do if the leader fails in Multi-Paxos for master-slave systems?
body: <p><strong>Backgound:</strong></p>
  <p>In section 3, named <em>Implementing a State Machine</em>, of Lamport's paper <a href="http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/past/03F/notes/paxos-simple.pdf" rel="nofollow noreferrer">Paxos Made Simple</a>, Multi-Paxos is described. Multi-Paxos is used in Google <a href="http://www.cs.utexas.edu/users/lorenzo/corsi/cs380d/papers/paper2-1.pdf" rel="nofollow noreferrer">Paxos Made Live</a>. (<strike>Multi-Paxos is used in <a href="https://www.usenix.org/legacy/event/usenix10/tech/full_papers/Hunt.pdf" rel="nofollow noreferrer">Apache ZooKeeper</a></strike>). In Multi-Paxos, gaps can appear:</p>
  <blockquote>
  <p>In general, suppose a leader can get <code>α</code> commands ahead--that is, it can propose commands <code>i + 1</code> through <code>i + α</code> commands after commands 1 through <code>i</code> are chosen. A gap of up to <code>α - 1</code> commands could then arise.</p>
  </blockquote>
  <p>Now consider the following scenario:</p>
  <blockquote>
  <p>The whole system uses <strong>master-slave</strong> architecture. Only the master serves client commands. Master and slaves reach consensus on the sequence of commands via Multi-Paxos. The master is the leader in Multi-Paxos instances. Assume now the master and two of its slaves have the states (commands have been chosen) shown in the following figure:</p>
  <p><img src="https://i.stack.imgur.com/iBzyu.jpg" alt="Master and Slaves" />.</p>
  <p>Note that, there are more than one gaps in the master state. Due to asynchrony, the two slaves lag behind. At this time, the master fails.</p>
  </blockquote>
  <p><strong>Problem:</strong></p>
  <blockquote>
  <ol>
  <li><p>What should the slaves do after they have detected the failure of the master (for example, by heartbeat mechanism)?</p>
  </li>
  <li><p>In particular, how to handle with the gaps and the missing commands with respect to that of the old master?</p>
  </li>
  </ol>
  </blockquote>
  <p><strong>Update about Zab:</strong></p>
  <p>As @sbridges has pointed out, <a href="https://www.usenix.org/legacy/event/usenix10/tech/full_papers/Hunt.pdf" rel="nofollow noreferrer">ZooKeeper</a> uses <a href="https://cwiki.apache.org/confluence/display/ZOOKEEPER/Zab+vs.+Paxos" rel="nofollow noreferrer">Zab</a> instead of Paxos. To quote,</p>
  <blockquote>
  <p>Zab is primarily designed for primary-backup (i.e., master-slave) systems, like ZooKeeper, rather than for state machine replication.</p>
  </blockquote>
  <p>It seems that Zab is closely related to my problems listed above. According to <a href="http://dl.acm.org/citation.cfm?id=1529978" rel="nofollow noreferrer">the short overview paper of Zab</a>, Zab protocol consists of two modes: recovery and broadcast. In recovery mode, two specific guarantees are made: <em>never forgetting committed messages</em> and <em>letting go of messages that are skipped</em>. My confusion about Zab is:</p>
  <blockquote>
  <ol start="3">
  <li>In recovery mode does Zab also suffer from the gaps problem? If so, what does Zab do?</li>
  </ol>
  </blockquote>