PDF Publication Title:
Text from PDF Page: 065
CHAPTER 3. KNOWN REVISIONS 65 Lemma 9 (Value uniqueness). If the value v is proposed in epoch e then no other value can also be proposed in e. We will now revise the proof of lemma 9 as follows. Lemma 17. Each acceptor will promise to at most one proposer for each epoch e. Proof of Lemma 17. Assume an acceptor has received prepare(e) and replied with promise(e,. . . ). The acceptor will have set its last promised epoch to e prior to sending the promise. Since the last promised epoch is monotonically increasing (lemma 6), then the acceptor’s last promised epoch will henceforth be ≥ e. Assume the acceptor receives prepare(e) from another proposer. For the acceptor to promise in e it must be have case that e > last promised epoch, yet last promised epoch is ≥ e thus the acceptor cannot accept the promise. Revised proof of lemma 9 using exclusive epochs by voting. It follows from Lemma 17 and the phase one quorum intersection requirement that: Corollary 17.1. At most one proposer will propose a value for a epoch. From this it follows that since each proposer will propose only one value for a given epoch then at most one value will be proposed for each epoch. Voting is used to allocate epochs in consensus algorithms such as Raft [OO14, §5.1]. 3.10 Proposal copying The pre-allocation of epochs in Classic Paxos (or exclusive access to epochs by voting) ensures that a unique proposer uses each epoch. It is important for safety (Lemma 9) to ensure that at most one value is used with each epoch. However, there is no requirement that only one proposer uses each epoch. Upon receipt of propose(e,v), an acceptor learns two important facts. Firstly, that a proposer has successfully executed phase one with epoch e and secondly, that the outcome of the value selection rules was that value v was chosen to be associated with epoch e. Given this information, another proposer can not only reuse the proposal mapping (e, v) but they can also skip phase one and proceed directly to phase two by dispatching propose(e,v) to the acceptors. We refer to this technique as proposal copying13. Below are two examples of how a proposer may learn (and therefore copy) past proposals.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 |