PDF Publication Title:
Text from PDF Page: 102
102 6.1. EPOCH AGNOSTIC ALGORITHM There are two routes for setting D[Q] = no, firstly if any acceptor in Q returns a nil proposal (Algorithm 18, lines 3-4) and secondly if a proposal for a greater epoch with a different value is returned (Algorithm 18, lines 6-7). Since all acceptors in quorum Q have accepted (e, v) prior to promising in succ(e) (Lemma 10) then none will return nil proposals ruling out the former (Lemmas 6 & 7). From lemma 8.1, we know that epoch e is the greatest epoch which will be returned in the proposals thus ruling out the latter. Therefore D[Q] ̸= no. Consider the case that D[Q] = w. This case requires that an acceptor in Q has accepted w in some epoch ≤ e (Lemma 8.1). Since all accepters in Q have accepted (e, v) then v = w due to value uniqueness (Lemma 9) and monotonicity of accepted epochs (Lemmas 6 & 7). 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 proposals in epochs from e to f (inclusive) are for v also. Assume that (succ(f),w) has been proposed. 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} (Property 16). The former case requires that D[Q] = no and the latter requires that either D[Q] = no or D[Q] = w when the proposer of succ(f) finishes phase one. We will now consider each case: Consider the case that D[Q] = no. There are two possibilities for setting D[Q] = no, firstly if any acceptor in Q returns a nil proposal (Algorithm 18, lines 3-4) and secondly if a proposal for a greater epoch with a different value is returned (Algorithm 18, lines 6-7). All acceptors in quorum Q have accepted (e, v) prior to promising in succ(f ) as succ(f ) > e (Lemma 10). Therefore none will return nil proposals, thus ruling out the former (Lemmas 6 & 7). From lemma 8.1, we know that epoch f is the greatest epoch which will be returned in the proposals. Likewise, from the monotonicity of accepted proposals (Lemmas 6 & 7), we know that acceptors in Q will return proposals from epochs ≥ e. Since the epochs e to f are limited to value v then a different value cannot be returned, ruling out the latter. Therefore D[Q] ̸= no. Consider the case that D[Q] = w.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 |