PDF Publication Title:
Text from PDF Page: 104
104 6.1. EPOCH AGNOSTIC ALGORITHM From Corollary 20.1, if a value v is decided with epoch ≤ e then v = w. Likewise, if a value v is decided with epoch ≤ f then v = x. Since e < f, then if a value v is decided with epoch ≤ e then v = w and v = x. This is only satisfied if w = x. Hence we have a contradiction. Lemma 20. If acceptors a1 and a2 send promise(g,e,w) and promise(g,f,x) (respectively) where e < f and w ̸= x then no decision is reached in epochs up to g (exclusive) by the quorums containing a1. Proof of Lemma 20. Assume that acceptor a1 sends promise(g,e,w) and acceptor a2 sends promise(g,f,x). Show that a decision (or decisions) could be reached in epoch up to g (exclusive) by a quorum Q containing a1. From Lemma 21, we know that no decision could be reached in epoch ≤ e. Since acceptor a1 has sent promise(g,e,w) then it cannot accept proposals from e to g (exclusive) thus no decision can be reached by quorum Q as a1 ∈ Q. 6.1.2 Progress Our epoch agnostic, quorum-based value selection algorithm relies on the fact that a set is a singleton, each time it uses the only function. This occurs in two places: line 17 of Algorithm 16 and line 9 of Algorithm 18. If this is not the case, the proposer algorithm will halt, reaching deadlock and violating our progress guarantees. In this section we will prove that this cannot occur. Lemma 22. A value is always returned by the assignment on line 9 of Algorithm 18. Proof of Lemma 22. We require that the set passed to only must be a singleton. We will prove this by contradiction by showing that neither an empty set or a set of cardinality > 1 could be passed to only on line 9 of Algorithm 18. Consider the case that for some quorum Q, {w ∈ V |∃a ∈ Q : R[a] = ( , w)} = ∅. This requires that for all acceptors in the quorum Q, R[a] = nil or R[a] = no. possibleValues is only called after R[a] ̸= no for least one acceptor from each quorum. The if-statement on line 3 was false, thus for all acceptors in Q, R[a] ̸= nil. Thus this case cannot occur. Consider the case that for some quorum Q, |{w ∈ V |∃a ∈ Q : R[a] = ( , w)}| > 1. This requires that (at least) two acceptors in the same quorum return proposes for different values. Since the if-statement on line 5 was false, these acceptors must have returned proposals for the same epoch (due to the total ordering of epochs). This case cannot occur due to value uniqueness (Corollary 9.1). Lemma 23. A value is always returned by the assignment on line 17 of Algorithm 16.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 |