PDF Publication Title:
Text from PDF Page: 051
CHAPTER 3. KNOWN REVISIONS 51 Algorithm 6: Acceptor algorithm for Classic Paxos with NACKs 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 while true do switch do case prepare(e) received from proposer if epro =nil∨e≥epro then epro ← e send promise(e,eacc,vacc) to proposer else /* e < epro so reply with NACK */ send no-promise(e,epro) 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 else /* e < epro so reply with NACK */ send no-accept(e,epro) to proposer proposal (5, B) has been accepted by all three acceptors (and thus has been decided). The proposer p1 begins phase one by dispatching prepare(0) to all acceptors. In Classic Paxos, this proposer would need to wait for a timeout and retry with proposal numbers 2, 4 and 6, thus requiring at least 4 round trip times. However, with NACKs the acceptor a1 can notify the proposer that its last proposed proposal number is 5 and the proposer p1 thus skips proposal numbers 2 and 4, allowing phase one to be completed in 2 round trips. NACK’s have replaced timeouts as we assume that messages are eventually delivered. We can therefore remove the synchrony assumptions from our progress proof. However, we still require there to be exactly one proposer for guaranteed progress, which we will later show can be implemented assuming synchrony (§3.4). Note that these two optimisations of restarting a proposal and skipping over epochs are distinct and could be used separately. For example, a proposer recovering after a long failure could opt to skip over some epochs to increase its likelihood of completing the proposer algorithm during its first try. It is also worthwhile noting that NACKs need not include the proposer’s epoch nor do we need separate messages for each phase. In fact, our existing accept message could be used for this purpose instead. We have chosen this approach for consistency with the existing messages and to ensure each message serves a single clearly defined purpose.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 |