StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The correctness of Multi-Paxos is conditioned on the requirement that the leader (<em>i.e.</em>, proposer) does not change between successive Paxos instances. From <a href="http://research.microsoft.com/en-us/um/people/lamport/pubs/lamport-paxos.pdf" rel="nofollow"><em>The Part-Time Parliament</em></a> Section 3.1 (The Protocol of the Multi-Decree Parliament):</p> <blockquote> <p>Logically, the parliamentary protocol [a.k.a. Multi-Paxos] used a separate instance of the complete Synod protocol [a.k.a. Paxos] for each decree number. However, <strong>a single president [a.k.a. proposer/leader] was selected for all these instances</strong>, and he performed the first two steps of the protocol just once.<br /><sub>[Added emphasis is mine.]</sub></p> </blockquote> <p>Therefore, Multi-Paxos makes the assumption that the case which you describe—when a second proposer comes online and believes he is (and always was) leader—will never happen. If such a case can happen, then one should not use Multi-Paxos. With respect to the second possibility—when the second proposer's <code>Prepare</code> did not reach the acceptor—the fact that the second proposer already sent out an <code>Accept!</code> means that it previously sent out a <code>Prepare</code> that was <code>Promised</code> by a quorum of acceptors. Since the acceptors already promised to the first proposer on round <code>N</code>, then the second proposer's <code>Prepare</code> must have been sent out prior to round <code>N</code>. Therefore, the final <code>Accept!(N+1,V2)</code> must have a counter <em>less than</em> <code>N</code>.</p> <p><strong>Edit:</strong> It should also be noted that this version of the protocol is not robust to <a href="http://en.wikipedia.org/wiki/Byzantine_fault_tolerance" rel="nofollow">Byzantine failure</a>:</p> <blockquote> <p>[The Paxon Parliament's protocol] does not tolerate arbitrary, malicious failures, nor does it guarantee bounded-time response.<br /><sub>—<em>The Part-Time Parliament</em>, Section 4.1</sub></p> </blockquote>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload