PDF Publication Title:
Text from PDF Page: 105
CHAPTER 6. VALUE SELECTION REVISED 105 Proof of Lemma 23. We require that Vdec, the set passed to only on line 17 of Algorithm 16 must be a singleton. Since the if-statement on line 14 was false, Vdec ̸= ∅. We must therefore prove that |{w ∈ V |∃Q ∈ Q2 : D[Q] = w}| ≤ 1 (line 10, Algorithm 18). Proof by contradiction. Assume that two (or more) quorums, Q and Q′, have different values for D[Q]. This requires that two acceptors, one in Q and one in Q′, promised with proposals for different values (line 9, Algorithm 18). If the epoch of these proposals are different, then the quorum with lower epoch would have D[Q] = no. Therefore, we require that the epochs of these proposals are the same, however, this cannot occur due to value uniqueness (Corollary 9.1). 6.1.3 Examples ConsiderthefollowingexamplewhereA={a1,a2,a3,a4,a5}andQ2 ={{a1,a2,a3},{a4,a5}}. A proposer is in epoch 5 and receives the following promises (in order): • promise(5,3,A) from a1, followed by • promise(5,nil,nil) from a2, followed by • promise(5,2,B) from a4 In Classic Paxos, the proposer must propose the value associated with the highest epoch, in this case A. However, utilising quorum-based value selection a proposer can learn that no decision has been reached in the epochs 0 − 4 and thus the proposer is free to choose any value for phase two. As a2 returned a nil proposal, the quorum {a1,a2,a3} cannot reach a decision in epochs 0 − 4. Likewise, since a1 returned the proposal (3, A) then the proposer learns that (2, B) cannot have been decided thus the quorum {a4, a5} also cannot reach a decision in epochs 0 − 4. Note that this generalisation is also useful when no promises include nil proposals. Consider the case when the proposer instead receives the following promises (in order): • promise(5,3,A) from a1, followed by • promise(5,1,A) from a2, followed by • promise(5,2,B) from a4. As before, the usual Paxos algorithm would require the proposer to propose A, however, with quorum-based value selection, the proposer is free to propose any value. This is because the quorum {a1, a2, a3} cannot have reached a decision since the proposal (2, B) means that the proposal (1, A) from a2 cannot have been decided. Likewise the quorum {a4, a5} cannot have reached a decision due to the proposal (3, A).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 |