PDF Publication Title:
Text from PDF Page: 046
46 2.7. PROGRESS Theorem 16. Provided the liveness conditions are satisfied, a proposer will eventually terminate and return a value v. Proof of Lemma 16. Consider a system which has reached GST. The proposer p may be at any stage of the proposer algorithm. Consider the case that p is at the start of the proposer algorithm. The proposer p will generate an epoch e ∈ E and dispatch prepare(e) to all acceptors. It follows from the liveness conditions that the majority of acceptors will receive prepare(e) within δm. Likewise, if e is greater than or equal to an acceptor’s last promised proposal number then it will promise within δa. Otherwise, the acceptor will not reply to the prepare message. Any promises sent by acceptors will be received within δm. If the proposer does not receive promises from a majority of acceptors after δa + 2δm + δd, the proposer will abandon epoch e and restart the proposer algorithm. The proposer p will generate a new epoch f where f > e (Property 5) and repeat phase one. As the acceptors will not receive any messages from other proposers, the last promised proposal number will not increase, except in response to p. Eventually, the proposer p will have generated a sufficiently large epoch that the majority of the acceptors will promise within δa + 2δm. The proposer will proceed to choosing a value. If no accepted proposals were returned by acceptors then the proposer is free to choose its own value. Otherwise, the proposer must choose the value associated with the highest epoch. Since the epochs are totally ordered and values are unique to epochs (Lemma 9.1) then proposer will always be able to choose a value v. The proposer then dispatches propose(e,v) to the acceptors and it is received within δm. Since the acceptors will not have updated their last promised epoch (as there are no other proposers) then the acceptors will accept the proposal. Since the proposer will receive accepts from the majority of acceptors within δa + 2δm, the value v is returned. Consider that case that p is elsewhere in the proposer algorithm. If the proposer p is in phase one of the proposer algorithm then it will proceed as described in the first case. If the proposer is in phase two of the proposer algorithm then it may timeout if its epoch is less then the majority of acceptors. In this case, the proposer will not receive accepts from the majority of acceptors before δa +2δm +δd, thus it will abandon the proposal and restart the proposer algorithm, as described in the first case. From Lemma 15, a weaker form of Lemma 16 is: Corollary 16.1. Provided the liveness conditions are satisfied, a value v will eventually be decided.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)