PDF Publication Title:
Text from PDF Page: 099
CHAPTER 6. VALUE SELECTION REVISED 99 which may have been decided, Vdec (line 13, Algorithm 16)1. If Vdec is empty, then no decision has been reached and the candidate value is proposed (lines 14-15, Algorithm 16). Otherwise, Vdec is a singleton and its only value is proposed (lines 16-17, Algorithm 16). The function only returns the only member from a singleton set. Classic value selection Algorithm 17: Classic algorithm for possibleValues. 1 2 3 func possibleValues(R): return {v ∈ V |∃f ∈ E : R[ ] = (f, v) ∧(∀a∈A:R[a]=no∨∃g∈E:R[a]=(g, )∧f≥g)} Algorithm 17 demonstrates the expected implementation of possibleValues, which is equiv- alent to Classic Paxos and our revisions. The algorithm returns either a set containing the value associated with the greatest proposal or an empty set if all proposals were nil2. Revised value selection Algorithm 18 gives the Quorum-based implementation of possibleValues. This algorithm is divided into two stages: firstly, it determines whether a decision may have been reached by each quorum and stores the result in D (lines 2-9, Algorithm 18). Then it uses D to determine whether an overall decision may have been reached (line 10, Algorithm 18). This algorithm for calculating quorum decision (lines 2-9, Algorithm 18) is not simply calculating the highest proposal in each quorum. Instead, it utilises the following two results: Lemma 19. If an acceptor a sends promise(f,e,w) where (e, w) = nil then no decision is reached in epochs up to f (exclusive) by the quorums containing a Lemma 19 is utilised by lines 3-4 (Algorithm 18) where a proposer sets the decision for a quorum to no if any of its acceptors returned nil promises. 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. 1It is not necessary at this point to return a set as it will be either empty or a singleton but we will utilise this later 2This algorithm cannot return a set of two or more values since the proposer must have received multiple proposals with the same epoch but different values. We have already shown that this is not possible (Corollary 9.1).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 |