PDF Publication Title:
Text from PDF Page: 042
42 2.6. SAFETY Proof of lemma 11. Both phases of Classic Paxos require participants from a majority of acceptors (Property 2). Any two majorities of acceptors will intersect, in other words they will have at least one acceptor in common. We can build upon lemma 11 to show the following: Lemma 12 (Weakened safety of future proposals). If a value v is decided in epoch e and value w is proposed in f where f > e then w must have been proposed in g where e ≤ g < f Proof of lemma 12. Assume value v is decided in epoch e and value w is proposed in f where f > e. The proposer in f will have proposed w after completing phase one and choosing w as a result of the value selection rules. From lemma 11, at least one acceptor must have sent both accept(e,v) to the proposer in e and promise(f, , ) to the proposer in f since e < f. From lemma 10, we know that this acceptor sent accept(e,v) prior to sending promise(f, , ) as e < f. Before the acceptor sent accept(e,v), they will have set their last promised epoch (Property 7) and last accepted epoch to e and set the last accepted value to v (Property 9). Since the last promised epoch was set to e and it is monotonically increasing (lemma 6), then the acceptor could only have accepted proposals for ≥ e after sending accept(e,v). Conversely, before sending promise(f, , ) the acceptor could only have accepted proposal for ≤ f (from lemma 8). Therefore, the proposer will only have updated its last accepted value for a proposal from e to f. Therefore the acceptor will have sent promise(f,g,x) where e≤gPDF 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 |