Distributed consensus

PDF Publication Title:

Distributed consensus ( distributed-consensus )

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

Text from PDF Page: 044

44 2.6. SAFETY Lemma 9 shows that at most one value will be proposed with any given epoch. Since it is necessary for a value to be proposed before it is decided, this means that at most one value can be decided with any epoch too. Consider the case that e ̸= f. Since there is a total ordering on epochs then either e < f or e > f. From the symmetry oftheorem14,wecanassumeef byswappingeandf. For a value to be decided, it must first be proposed, therefore a stronger theorem is theorem 13. Now that we have proven the safety of the decided values, we will prove that only decided values will be returned by the proposers. Lemma 15 (Safety of learning). If the value v is returned by a proposer then v has been decided. Proof of Lemma 15. Consider a proposer p who has returned v. Prior to returning v, p must have received accept(e) for some epoch e from a majority of acceptors (Property 3). We know accept(e) must have been sent in response to propose(e,v) from proposer p (Property 1). Therefore the majority of acceptors must have accepted the proposal (e, v) so by definition the value v must have been decided (Property 9). Result Monotonicity of promises (6) Relation between acceptor epochs (7) General promise format (8) Value uniqueness (9) Message ordering (10) Quorum intersection (11) Weakened safety of future proposals (12) Base case for safety of future proposals (12.1) Inductive case for safety of future proposals (12.2) Safety of future proposals (13) Safety for Classic Paxos (14) Safety of learning (15) Properties: 6, 7, 10 8, 10 8 1 6, 7, 8, 9 2 4, 7, 9 Other results: 6 7 6 11, 8, 10, 6 9, 12 9, 12 12.1, 12.2 9, 13 1, 3, 9 Table 2.3: Use of algorithm properties to prove the safety of Classic Paxos

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