PDF Publication Title:
Text from PDF Page: 137
CHAPTER 7. EPOCHS REVISED 137 Algorithm 31: Fast path - Proposer algorithm for Multi-path Paxos with recovery 1 2 3 4 5 6 7 8 9 /* Start of Phase 2 for proposal (emin,γ) */ QA ← ∅ send propose( emin,γ) to acceptors while |QA| < 3na do 4 switch do case accept( emin,γ) received from acceptor a QA ← QA ∪ {a} case timeout goto slow path return γ By using counting quorums of size k = 3na for emin then we can use strict majority 4 quorums for all other epochs. Such an algorithm would satisfy the same progress guarantees as Classic Paxos but with an improved best case; a decision in one round trip to 34 of acceptors. The proposer algorithm would first try to get acceptors to accept phase two of emin (fast path) and fall back to majority agreement for both phases of a subsequent epoch if unsuccessful (slow path). We can utilise Paxos revision C to optimise algorithm 32. For all epochs e where e ̸= succ(emin), if a promise is received with a proposal (f,v) where e = succ(f) then the proposer can proceed to phase two of epoch e to propose v. Similarly, for the epoch succ(emin), we can also proceed to phase two when at least na +1 4 acceptors have promised; and at most one unique proposal was received with the promises. Fast Paxos (outlined in §3.12) is a special case of Hybrid epochs, where fast epochs are shared by recovery and classic epochs are pre-allocated/voted. In Fast Paxos, all phase one quorums are of size kc, regardless of the promises returned during phase one. This is equivalent to always waiting for the upper bound on the number of promises needed in Paxos with epochs by recovery. Thus one of the implications of epochs by recovery (other than its generality) is that phase one of Fast Paxos can be completed after fewer promises, with a minimum of na − kf + 1 promises needed. 7.5 Summary In this chapter, we have demonstrated various alternatives to pre-allocation or phase one voting for allocation of epochs between proposers. The methods covered included dynamic epoch allocation by an allocator, allocating epochs by value instead of by proposer and sharing epochs by recovery. These methods can be used individually or in combination.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 |