Distributed consensus

PDF Publication Title:

Distributed consensus ( distributed-consensus )

Previous Page View | Next Page View | Return to Search List

Text from PDF Page: 043

CHAPTER 2. CONSENSUS & CLASSIC PAXOS 43 Corollary 12.2 (Inductive case for safety of future proposals). If the value v is decided in epoch e and the proposals from e (exclusive) to f (inclusive) are limited to the value v then if value w is proposed in g such that g = succ(f) then v = w. Theorem 13 (Safety of future proposals). If the value v is decided in epoch e and the valuewisproposedinepochf suchthate e which reach a decision, will decide upon the same value. Proof of theorem 13. Assume the value v is decided in epoch e. We will prove this by induction. Firstly, we will demonstrate that no proposer will propose a different value using proposal succ(e). We cannot know if a decision will be reached in epoch succ(e) but if one is reached, it will always decide on v, the same value as e. In other words, the successor of proposal e is limited to v. (Base case) If the value w is proposed in epoch f such that f = succ(e) then v = w. This was proven by corollary 12.1. Next, we will demonstrate that the successor of a sequence of limited proposals following a decided proposal is also limited to the same value. (Inductive case) If the proposals from e to f are limited to the value v then if value w is proposed in epoch g such that g = succ(f) then v = w. This was proven by corollary 12.2. By induction, we see that if the value v is decided in epoch e then all subsequent proposals will be limited to value v. Therefore proving theorem 13 and thus theorem 14. Proof of safety of Classic Paxos Overall, to prove the safety of Paxos, we show the following: Theorem 14 (Safety for Classic Paxos). If the value v is decided in epoch e and the value wisdecidedinepochf thenv=w This could also be stated as if a value v is decided then all epochs are limited to v. Proof of theorem 14. Consider the case that e = f.

PDF Image | Distributed consensus

PDF Search Title:

Distributed consensus

Original File Name Searched:

UCAM-CL-TR-935.pdf

DIY 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