PDF Publication Title:
Text from PDF Page: 094
94 5.4. EXAMPLES Thus we must provide a revised proof for Lemma 12 to verify the safety of Paxos revision C. Lemma 12 (Weakened safety of future proposals). If a value v is decided in epoch e and value w is proposed in f where f > e then w must have been proposed in g where e ≤ g < f Revised proof of lemma 12. Assume value v is decided in epoch e and value w is proposed in f where f > e. The proposer in f will have proposed w after completing phase one and choosing w as a result of the value selection rules. From theorem 18, we know that either at least one acceptor which accepted proposal (e, v) will be required to promise in f or an acceptor will promise with a proposal from epoch e or a subsequent epoch. In either case, the acceptor will reply with promise(f,g,x) where e ≤ g < f and x is the value proposed in g (Lemmas 6 & 10, Corollary 8.1). According to the value selection rules (Property 4), the proposer of f must therefore propose either the value x or another value y from the proposal (h, y) such that h > g. Regardless of whether w = x or w = y, w must have been proposed in an epoch between e (inclusive) and f (exclusive). The proof of non-triviality for Classic Paxos (§2.5) still applies to Paxos revision C. 5.4 Examples The implications of this result apply even when the quorum system used is agnostic to the epoch. For example, we can extend the proposer algorithm for Classic Paxos to test whether a promise message includes a proposal for the predecessor of the current epoch. If this is the case, the proposer can proceed directly to phase two without waiting for a phase one quorum. Table 5.1 shows how line 6 of Algorithm 15 can be simplified if phase two quorums are epoch agnostic. RevisionA ∃Q∈Q2 :QP ∩Q=∅ Revision B same as A and e ̸= emin Revision C same as B and e ̸= succ(emax) Table 5.1: Simplified while conditions for line 6, Algorithm 15. Figure 5.1 shows a simple example of this using the same scenario as our first Classic Paxos example (Figure 2.2). The proposer p2 proceeds to phase two of epoch 1 after receiving a promise from one acceptor a3 since this promise included the proposal (0, A) from the predecessor epoch.PDF 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 | RSS | AMP |