PDF Publication Title:
Text from PDF Page: 039
CHAPTER 2. CONSENSUS & CLASSIC PAXOS 39 2.5 Non-triviality Firstly, for Classic Paxos to solve distributed consensus it must satisfy non-triviality. Let Γ denote the set of candidate values proposed by proposers, thus non-triviality is specified as follows: Theorem 4 (Non-triviality of decided values). If the value v is decided then v ∈ Γ. In Classic Paxos, for a value to be decided, it is necessary for the value to first be proposed. Therefore a stronger version of theorem 4 is: Theorem 5 (Non-triviality of proposed values). If the value v is proposed then v ∈ Γ. Proof of theorem 5. Consider a proposer in phase two which proposes the value v with epoch e. We will let V denote the set of values which have been proposed so far, thus initially V = ∅. We show by induction over the set of proposed values V that all proposed values are candidate values, thus V ⊆ Γ Base case (initial state): Initially, before any values are proposed, V = ∅ and ∅ ⊆ Γ. Base case (the first proposal): Consider the first proposer to propose a value. We will denote this value as v. The value v must have been chosen according to the algorithm’s value selection rules. Since no values have yet been proposed, no proposals will be received with the promises in the proposer’s phase one. The first proposer will therefore always propose its own candidate value, v ∈ Γ thus V = v and V ⊆ Γ (Property 4). Inductive case: We assume that V ⊆ Γ and that the next proposer proposes the value w. We will show that w ∈ Γ thus V ⊆ Γ remains true. The value w must have been chosen according to the algorithm’s value selection rules. It is either the case that no proposals were received during the proposer’s phase one so the proposer proposed its own candidate value, w ∈ Γ; or one (or more) proposals were received with the promises in the proposer’s phase one. The proposer will therefore propose the value w associated with highest epoch returned (Property 4). All proposals received must have been first proposed by a proposer. Therefore V remains unchanged and V ⊆ Γ remains true. 2.6 Safety In order for the Classic Paxos algorithm to solve distributed consensus we must show that all possible executions of the algorithm are safe. In other words, if a value has been decided then no other value can also be decided. In this section, we will prove this propertyPDF 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 |