PDF Publication Title:
Text from PDF Page: 041
CHAPTER 2. CONSENSUS & CLASSIC PAXOS 41 From this, we know that the greatest promise a proposer in e could receive is from the predecessor epoch14. Therefore according to the value selection rules (Property 4): Corollary 8.2 (Predecessor proposals). If a proposer in e receives promise(e,f,v) where e = succ(f) during its phase one then the proposer will propose value v. Lemma 9 (Value uniqueness). If the value v is proposed in epoch e then no other value can also be proposed in e. Proof of lemma 9. At most one proposer is able to use each epoch (Property 1). Each proposer will decide a value to propose and send a propose message to the acceptors with that value. A proposer will not use the same epoch twice. If a proposer fails during the proposal and does not have knowledge of the value chosen then it will start again with a new epoch. As a consequence of lemma 9: Corollary 9.1 (Value uniqueness in promises). For any two promises, promise( ,f,v) and promise( ,g,w), if f = g then v = w. As a result, we know that a proposer will not receive multiple proposals in its phase one which have the same epoch but different values. Lemma 10 (Message ordering). If a series of messages has been sent by an acceptor15, then the message epochs are a partial ordering on the order in which the messages were sent. This applies regardless of whether the messages are all promises, all accepts or a combination of both. Proof of lemma 10. Consider two messages which have been sent by a acceptor with epochs e and f such that e < f. Assume that the message with epoch f was sent first. When the acceptor sent the first messages, the last promised epoch, epro, will have been set to f, regardless of whether the message was promise or accept (Property 7). Lemma 6 shows that the last promised epoch is monotonically increasing so henceforth epro ≥ f. The second message has epoch e and is sent by the acceptor in response to a prepare or propose request, provided that e ≥ epro (Properties 6,8 & 9). This requires e = f, contradicting the assumption that e < f. Therefore the message with epoch f must be sent after the message with epoch e. Lemma 11 (Quorum intersection). If a value v is decided in epoch e then at least one acceptor which accepted proposal (e,v) will be required to promise in any future proposals > e. 14Note that when e = min(E) no such predecessor exists. 15Whilst we do not prove it here, message ordering also applies to proposers.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 |