PDF Publication Title:
Text from PDF Page: 109
CHAPTER 6. VALUE SELECTION REVISED 109 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. The value w which is proposed in succ(f) 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). Consider the case that Vdec = ∅. This requires that for all quorums, for epochs less than succ(e), D[Q] = no, including the quorum Q which accepted (e,v). Due to message ordering (Lemma 10) and the monotonicity of promises (Lemmas 6 & 7), D[Q] will not be assigned to no by either lines 4-5 or 6-7. Since f is the greatest epoch which will be returned with a promise (Lemma 8.1) and all proposals for epochs e to f are for value v, D[Q] will not be assigned by lines 8-9. Therefore, the case that Vdec = ∅ cannot occur. Consider the case that Vdec = {w}. This requires that for all quorums, for epochs less than succ(e), either D[Q] = w or D[Q] = no. We have already shown that for the quorum Q which accepted (e, v), D[Q] ̸= no thus D[Q] = w. As before, f is the greatest epoch which will be returned with a promise (Lemma 8.1). Therefore at least one acceptor in Q will have promised with the proposal (h,w)forsomehwheree≤h≤f andsomevaluew.Asallproposalsforepochsetof are for the value v then it must be case that v = w. 6.2.2 Progress Unlike our epoch agnostic algorithm, in our new algorithm (Algorithm 19) the proposer re-calculates Vdec after each promise is received. The proposer then uses the cardinality of Vdec to determine when phase one is completed. In contrast to the algorithms thus far, it is not clear that the algorithm will always make progress under the expected liveness conditions. In this section, we therefore prove that the proposer’s phase one will terminate once the quorum intersection requirements have been satisfied. Lemma 24. If a proposer in epoch e has received sufficient promises to satisfy revision C quorum intersection, then for all quorums of previous epochs D[Q] ̸= nil.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 (Standard Web Page)