PDF Publication Title:
Text from PDF Page: 063
CHAPTER 3. KNOWN REVISIONS 63 Various mechanisms for allocating epochs are demonstrated by algorithms such as Sim- ple Paxos [Lam01a, §2.5], Chubby [CGR07], VRR [LC12, §4] and Moderately Complex Paxos [VRA15] 3.9 Phase one voting for epochs It has long been known that Classic Paxos does not require that epochs are unique if acceptors require that a proposer’s epochs be strictly greater than the last promised proposal. This means that at most one proposer will reach phase two for a given epoch, since reaching phase two requires a proposer to have already reached majority agreement for phase one, thus guaranteeing uniqueness. Algorithm 10: Acceptor algorithm for Classic Paxos with voting state : 1 2 3 4 5 6 7 8 9 10 11 • plst: last proposer promised to, plst ∈ P (persistent) while true do switch do case prepare(e) received from proposer p if (epro =nil)∨(e>epro)∨(e=epro ∧p=plst)then epro ←e,plst ←p send promise(e,eacc,vacc) to proposer case propose(e,v) received from proposer if epro =nil∨e≥epro then epro ← e vacc ←v,eacc ←e send accept(e) to proposer We can implement exclusive epochs by voting by adding the requirement to promises that if the epoch from the prepare message e is equal to the last promised epoch epro then the proposer p must be the same as the proposer who was previously promised plst. This revised acceptor algorithm is show in Algorithm 10. The proposer algorithm remains almost unchanged, except that proposers no longer need to be allocated a disjoint subset of epochs, thus proposer can use any epoch E = E. Figure 3.4 gives an example of Classic Paxos with voting. In contrast to our first Classic Paxos example (Figure 2.2), proposer p2 initially uses proposal number 0 (instead of 1). Proposer p2 times out as p1 has already completed phase one for proposal number 0. The proposer p2 then tries proposal number 1 and proceeds as before. Recall that in the proof of safety of Classic Paxos we used the following lemma: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 (Standard Web Page)