PDF Publication Title:
Text from PDF Page: 119
CHAPTER 7. EPOCHS REVISED 119 Solution 1: Therefore, we require that the phase two quorums of a given epoch intersect, stated as: ∀Q,Q′ ∈Qe2 :Q∩Q′ ̸=∅ (7.1) Problem 2: Secondly, a value which has already been accepted by a phase two quorum can be overwritten by different values with the same epoch, violating protocol safety. Solution 2: This can be addressed by adding a condition to phase two that a proposal (e,v) is only accepted if either the new proposal epoch is higher than the previous one e > eacc or the new proposal is the same as the previous one (e, v) = (eacc, vacc). In other words, an acceptor cannot overwrite an accepted value with the same epoch. Problem 3: Thirdly, the approach described thus far may reach a state from which it is unable to make progress under the usual liveness conditions. We refer to this as value collision. Recall that the value selection rules of Paxos require that a proposer chooses the value associated with the highest epoch received in phase one. In the example, the proposer has received two promises in phase one of the algorithm, with the same epoch but two different values. The proposer must choose which of the two values to propose in its phase two. When choosing a value, a proposer must know for certain that no other value has been decided. In this case, however, the proposer cannot know which order the prepare messages were received by other acceptors, if they have been received at all. Therefore, since the proposer cannot safely proceed through the algorithm, it cannot make progress. Solution 3: This example demonstrates the case for strengthening the quorum intersection requirements when using shared epochs. The previous quorum intersection requirement 4.6 is not necessarily sufficient to make progress as we have seen. The following intersection rule, given in 7.2 is sufficient to always make progress. In Paxos revisions B, we required that a phase one quorum intersects with any previous phase two quorums. Now, we require that a phase one quorum intersects with the intersection of any phase two quorums for a previous epoch. More formally, for each epoch e the following intersection requirement is sufficient: ∀Q∈Qe1,∀f∈E:fPDF 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 |