PDF Publication Title:
Text from PDF Page: 083
CHAPTER 4. QUORUM INTERSECTION REVISED 83 Similar to the safety proof of Paxos revision A (§4.1.2), we now provide a revised proof of lemma 11 which can be substituted into the proof of Classic Paxos for a proof of safety for Paxos revision B. Revised proof of lemma 11. Assume the value v is decided in epoch e, thus some phase two quorum of acceptors Q ∈ Qe2 would have accepted the proposal (e, v). Consider a proposal in epoch f where f > e. Before a value could be proposed in f, a phase one quorum of acceptors for proposal in epoch f, Q′ ∈ Qf1 must promise to the proposer of f (Property 13). Since f > e, we can apply equation 4.6 to see that any two quorums will intersect therefore the quorums will always have at least one acceptor in common. Revision A generalises over Classic Paxos by weakening the quorum intersection require- ments depending on the algorithm phase the quorum is used with. In turn, Revision B generalises over Revision A (and therefore Classic Paxos) by weakening the quorum intersection requirements depending on the epoch and phase that the quorum is used with. Like our proof of safety for Classic Paxos, Lamport’s original proof did not use the full strength of the assumptions that were made, namely that all quorums will intersect. This result does not dispute that Classic Paxos is a solution to distributed consensus but does demonstrate that the algorithm is needlessly conservative in its approach. Classic Paxos is a specific case of Paxos revision A and in turn of, Revision B, which adds the requirement for quorum intersection within each phase and regardless of epoch. 4.2.3 Examples A key implication of this result is that for the minimum epoch emin where emin = min(E), there is no phase one quorum intersection requirement. The practical application of this is that a proposer with epoch emin may skip phase one and proceed directly to proposing their own value γ in phase two using propose(emin,γ). As epochs are unique to proposers, only one proposer will be able to take advantage of this. Assuming this proposer is the first to propose a value and no other proposers try to propose concurrently, this proposer can decide a value in one round trip, as demonstrated in Figure 4.3. Figure 4.3 shows the same example as Figure 2.2, however the proposer p1 is now able to skip phase one and reach agreement in just one phase. This result is functionally equivalent to starting a system in a state such that one proposer has already executed phase one with all acceptors. This technique was utilised in the Coordinated Paxos algorithm in Mencius [MJM08, §4.2] Counterintuitively, it is now possible that the commit point may have already been reached and that a proposer (with a lower epoch such as emin) does not see the chosen value duringPDF Image | Distributed consensus
PDF Search Title:
Distributed consensusOriginal File Name Searched:
UCAM-CL-TR-935.pdfDIY PDF Search: Google It | Yahoo | Bing
Cruise Ship Reviews | Luxury Resort | Jet | Yacht | and Travel Tech More Info
Cruising Review Topics and Articles More Info
Software based on Filemaker for the travel industry More Info
The Burgenstock Resort: Reviews on CruisingReview website... More Info
Resort Reviews: World Class resorts... More Info
The Riffelalp Resort: Reviews on CruisingReview website... More Info
CONTACT TEL: 608-238-6001 Email: greg@cruisingreview.com (Standard Web Page)