PDF Publication Title:
Text from PDF Page: 101
CHAPTER 6. VALUE SELECTION REVISED 101 words, the classic approach may propose a value that the quorum-based approach knows to be undecided4. In this implementation, the proposer always proposes its candidate value if no decisions had been reached. However, the proposer could safely propose any value it has seen thus quorum-based value selection is a generalisation over the classic value selection rules. 6.1.1 Safety We will begin by proving the safety of our epoch agnostic, quorum-based value selection algorithm. Recall that all our earlier proofs of safety depend upon Property 4: 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. This property is implemented by our na ̈ıve implementation of possibleValues (Algorithm 17) but not by our quorum-based implementation (Algorithm 18). For quorum-based Paxos, we revise the value selection rule as follows. All other Paxos revision A properties still hold. 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 ∈ Q2 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). The former case requires that D[Q] = no and the latter requires that either D[Q] = no or D[Q] = w when the proposer of succ(e) finishes phase one. We will now consider each case: Consider the case that D[Q] = no. 4The converse is not true.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)