PDF Publication Title:
Text from PDF Page: 108
108 6.2. EPOCH DEPENDENT ALGORITHM revisions B and C. 6.2.1 Safety In this section, we will prove the safety of our epoch dependent, quorum-based value selection algorithm. As with our safety proof for the epoch agnostic algorithm (§6.1.1), we will substitute Property 4 with Property 16. Property 4. Proposers must choose a value to propose according to the value selection rules. If no previously accepted proposals were returned with promises then any value can be chosen. If one or more previously accepted proposals were returned then the value associated with the highest epoch is chosen. Property 16. Proposers must choose a value to propose in epoch e according to the value selection rules. If Vdec is an empty set then any value can be chosen. Otherwise if Vdec is a singleton then its only value is chosen. We begin be revising our proof of Corollary 12.1. Corollary 12.1 (Base case for safety of future proposals). If the value v is decided in epoch e and the value w is proposed succ(e) then v = w. 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 there exists a quorum Q ∈ Qe2 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 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 by either lines 4-5 or 6-7. Due to value uniqueness (Lemma 9) and promise format (Lemma 8.1), D[Q] will not be assigned by lines 8-9. Therefore, 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 which accepted (e, v), D[Q] ̸= no thus D[Q] = w. Since e is the greatest epoch which will be returned with a promise (Lemma 8.1) then w = v.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 |