PDF Publication Title:
Text from PDF Page: 055
CHAPTER 3. KNOWN REVISIONS 55 We can increase the likelihood of phase two bypass using the following techniques: • If a proposer has received many of the same proposals in phase one but not quite reached the ⌊na/2⌋ + 1 copies needed to bypass phase two then it may opt to wait for further promises before proceeding. The timeout would be required to limit this wait to maintain progress guarantees.3 • A proposer can concurrently start phase two and continue waiting for promises in phase one. If sufficient promises with the same proposal are received before phase two is completed then the remainder of phase two can be bypassed. • Instead of tracking whether the greatest proposal is returned by the majority, pro- posers could track all proposals returned. • Proposers could re-use promises from previous epochs when tracking the propos- als returned for phase two bypass. This could involve storing previously received proposals to persistent storage, however this is not necessary. • Proposers could include proposals from NACKs, again regardless of epoch or message name, when tracking the proposals returned for phase two bypass. • Acceptors could store all accepted proposals instead of just the last accepted proposal. Acceptors could then include all previously accepted proposals in promise messages (and NACKs), providing proposers with additional information about the state of the system4. 3.3 Termination In Classic Paxos, even with bypassing phase two enabled, a proposer must communicate with a majority of acceptors to learn the decided value. This means that the liveness condi- tions for progress are necessary as well as sufficient for progress. In other words, regardless of the state of the system, the majority of acceptors must be up and communicating for a proposer to execute its algorithm and return a decided value. We can improve this by adding an optional phase three to Classic Paxos in which the acceptors learn the value has been decided. The acceptors can then notify future proposers that the value has been decided, enabling the proposer to return a decided value without waiting upon the majority of acceptors. Adding phase three to Classic Paxos serves an important purpose that may not be immediately apparent, namely that the liveness conditions are no longer necessary for progress. With this variant, Classic Paxos can make progress provided either a majority of acceptors are up or at least one acceptor who has 3In the previous section on negative responses (§3.1), we saw that a proposer may opt to retry a proposal early, prior to timing out. We now see that a proposer may opt to wait longer before proceeding to phase two. 4Some papers such as [VRA15] described this approach as Paxos and describe storing only the last accepted proposals as an optimisation.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 |