PDF Publication Title:
Text from PDF Page: 136
136 7.4. HYBRID EPOCH ALLOCATION As described in section 7.1, we could extend the allocator to store the value associated with the epoch assigned by the service. Effectively, the allocator stores the primary copy of the value and the acceptors store the backup copy. If the allocator is available, the proposers can take the fast path. First, the proposers get/set the primary copy of the value on the allocator (phase zero) then they back up the value to a quorum of acceptors Qemin (phase one)18. Otherwise, the proposer takes the slow path, executing the classic 2 two phase proposer algorithm over the acceptors to update the backup copies of the value. Note, that this algorithm provides a new progress guarantee. If the system is synchronous and both the allocator and an acceptor quorum Q ∈ Qemin are live, then proposers are 2 guaranteed to terminate in two round trips (one to the allocator and one to acceptors)19. This is because the allocator acts as a serialisation point, preventing duelling between proposers. 7.4.2 Multi-path Paxos using value-based allocation Value-based allocation of epochs requires that candidate values be limited to a known range. This restriction can be weakened using Multi-path Paxos to permit values outside the known range. The first n epochs are allocated to values within the known range of size n, the most likely values should be allocated the lower epochs with the most common value assigned to emin. All epochs after n are assigned to proposers by pre-allocation. If a proposer has a candidate value from the known range then the proposer can use the value assigned epoch. If this is unsuccessful or if the proposer has a candidate value outside the known range then the proposer can fall back to using the epoch assigned by pre-allocation. As before, this algorithm provides a new progress guarantee. If all proposers are proposing the same value then they are guaranteed to terminate in two round trips (or one round trip for the value associated with the minimum epoch) even in an asynchronous system20. This is not the case for Classic Paxos where proposers proposing the same value could duel indefinitely. 7.4.3 Multi-path Paxos using recovery Algorithms 31 & 32 shows an example hybrid algorithm consisting of epochs by recovery for emin (fast path) and pre-allocation for all other epochs (slow path). Algorithm 31 is a fast path proposer algorithm, Algorithm 32 is the slow path proposer algorithm and the acceptor algorithm is the same as for epochs by recovery (Algorithm 24). 18Note that unlike the SAA, proposer cannot always read the value stored on the allocator to learn the decided value 19This requires the system to have been synchronous since startup. 20This statement assumes that NACKs are used instead of timeoutsPDF 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 |