PDF Publication Title:
Text from PDF Page: 127
CHAPTER 7. EPOCHS REVISED 127 Algorithms which use epochs by recovery need not be complex. For example, the simplest quorum system contains a single fixed quorum, Q. If we let Q2 = {Q} then one promise from an acceptor in Q will always be sufficient to complete phase one, as shown in Algorithm 27. This algorithm may be simple but it does require all acceptors in Q to be up for liveness. This algorithm is similar to the first iteration of All aboard Paxos (§4.3.2) with the added flexibility that acceptors may use any epoch. Example: Fixed quorums for epochs by recovery Instead, Algorithm 28 assigns a single quorum, Qe to each epoch e such that ∀e ∈ E : Qe2 = {Qe}. All phase two quorums in epoch e are guaranteed to intersect at all acceptors in Qe, therefore a single promise from an acceptor in Qe is sufficient to satisfy the strength- ened intersection requirement. We have also applied Paxos revision C to this algorithm. Algorithm 27 is a special case of Algorithm 28 where each epoch is assigned the same quorum. Note that this proposer algorithm is very similar to Paxos revision C proposer algorithm when each epoch has only one phase two quorum. The key difference here is that receiving a proposal (f, v) is only sufficient to satisfy the quorum intersection requirement for epochs strictly less than f, unlike Paxos revision C where this was sufficient for epoch less than or equivalent to f. Aside from this, shared epochs are effectively free as no additional promises are needed. Example: Counting quorums for epochs by recovery Our algorithm for epochs by recovery (Algorithm 25) was quorum system agnostic. In this section, we specialise the algorithm for counting quorums, where any set of k or more acceptors is a phase two quorum. A pseudocode proposer algorithm is shown in Algorithm 29. The acceptor remains unchanged. Since we require phase two quorum intersection (Equation 7.1) then we require that 2k > na where na is the number of acceptors and k is the quorum size. There are two conditions which must be satisfied to complete phase one (line 9, Algorithm 29). Firstly, at least na − k + 1 promises must have been received. This condition satisfies the usual revision A quorum intersection requirement (Equation 4.6). Secondly, at most one value can be a member of Vdec. After the first condition has been satisfied, then Vdec represents the set of value which maybe decided in emax. A value v is only included in Vdec if the proposal (emax,v) has been returned by sufficient acceptors that (emax,v) would be decided if all remaining acceptors (na − |QP |) also return the proposal (emax, v).10 10This pseduocode is re-calculating Vdec after receiving each message, this could be done more effectively by updating Vdec incrementally.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 |