PDF Publication Title:
Text from PDF Page: 124
124 7.3. EPOCHS BY RECOVERY Revised proof of Corollary 12.1. Assume that (e, v) has been decided and (succ(e), w) has been proposed. Since (e, v) has been decided thus there exists a quorum Q ∈ Q2 such that all acceptors have accepted (e, v). The value w which is proposed in succ(e) will have been chosen in one of two ways: either Vdec was empty (and w was the proposer’s candidate value) or Vdec = {w} (Property 19). The former case requires that D[Q] = no and the later requires that either D[Q] = no or D[Q] = w when the proposer of succ(e) finishes phase one. We will now consider each case Consider the case that D[Q] = no. Since all acceptors in quorum Q have accepted (e, v) then none will return nil proposals with promises (lines 3/4). Likewise, acceptors will not accept another proposal from e (lines 9/10). Thus another acceptor must have returned a proposal for an epoch > e (lines 8-10, Property 19). This epoch must be succ(e). Consider the case that D[Q] = w. Since all acceptors in quorum Q have accepted (e,v) either w = v or w = x where (succ(e), x) has been proposed. We have seen that either w = v or w = x where x is another value which has been proposed in epoch succ(e). If this is first value proposed in succ(e) then it must be the case that w = v. If all other values proposed in succ(e) are v then w = v. They we have proven 12.1 by induction. Next we revise our proof of Corollary 12.2. Corollary 12.2 (Inductive case for safety of future proposals). If the value v is decided in epoch e and the proposals from e (exclusive) to f (inclusive) are limited to the value v then if value w is proposed in g such that g = succ(f) then v = w. Revised proof of Corollary 12.2. Assume that (e, v) has been decided thus there exists Q ∈ Q2 such that all acceptors have accepted (e, v). Assume that all values proposed in epochs from e to f are for v also. Assume that value w has been proposed by a proposer in epoch succ(f). The value w will have been chosen in one of two ways: either Vdec was empty (and w was the proposer’s candidate value) or Vdec = {w}. Consider the case that Vdec = ∅. For all quorums including Q, D[Q] = no. Given that all acceptors in Q have accepted (e,v), it is only possible for D[Q] = no if an acceptor returns promise(succ(f),h,x) where h > e and x ̸= v (Property 19). As all values proposed in epochs from e to f are for v then h = succ(f). By induction, we can see that x = v thus this case cannot occur.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 |