PDF Publication Title:
Text from PDF Page: 100
100 6.1. EPOCH AGNOSTIC ALGORITHM Algorithm 18: Quorum-based algorithm for possibleValues. 1 2 3 4 5 6 7 8 9 10 state : • D: for each quorum, Q, the outcome of previous proposals, either: – no: no decisions have been reached in Q – v: if decision(s) were reached in Q, value v was decided func possibleValues(R): foreach Q ∈ Q2 do if ∃a∈Q:R[a]=nil then /* if acceptor in quorum returns nil then no decision */ D[Q] ← no elseif∃a∈Q,∃f,g∈E,∃w,x∈V: R[a]=(f,w)∧R[]=(g,x)∧g>f∧x̸=wthen /* if two acceptors return proposals with different values then no decision for quorums containing the acceptor with the lower proposal */ D[Q] ← no else /* all proposals returned by quorum are for the same value thus this value maybe decided */ D[Q] ← only({w ∈ V |∃a ∈ Q : R[a] = ( , w)}) return{w∈V|∃Q∈Q2 :D[Q]=w} Lemma 20 is utilised by lines 5-7 (Algorithm 18) where a proposer sets the decision for a quorum to no if any acceptor returned a proposal with a greater epoch and different value to one returned by an acceptor within the quorum. For a given quorum, Q, if neither of the previous cases (lines 3-7, Algorithm 18) are satisfied then a decision may have been reached in Q. When this case is reached (lines 8-9), then exactly one value has been returned with all the promises from acceptors in Q. We know this because at least one acceptor in Q has promised3, all acceptors in Q which promised returned a non-nil proposal and if two acceptors returned different values then this case would not be reached. If a value has been decided, then both implementations of possibleValues will return the decided value. If no value has been proposed, both approaches will return an empty set. If exactly one acceptor from each quorum promises then both approaches return same results. However, if more promises are received, the classic implementation of possibleValues may return a value, where the quorum-based implementation may return an empty set. In other 3Since possibleValues is only called after at least one acceptor from each quorum has replied.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 |