PDF Publication Title:
Text from PDF Page: 038
38 2.4. PROPERTIES 2.4 Properties Before we reason about the safety and liveness of Classic Paxos, we divide the algorithm into a set of properties. These properties will identify how specific components of the algorithm are utilised in subsequent proofs. In later chapters, we will modify the Classic Paxos algorithm, using these properties we will be able to determine which proofs are still valid and which need revising. The key properties of the Classic Paxos proposer algorithm are as follows: Property 1. Proposers use unique epochs for each proposal. Property 2. Proposers only propose a value after receiving promises from ⌊na/2⌋ + 1 acceptors. Property 3. Proposers only return a value after receiving accepts from ⌊na/2⌋ + 1 accep- tors. Property 4. Proposers must choose a value to propose according to the value selection rules. If no previously accepted proposals were returned with promises then any value can be chosen. If one or more previously accepted proposals were returned then the value associated with the highest epoch is chosen. Property 5. Each epoch used by a proposer is greater than all previous epochs used by the proposer. The key properties of the acceptor algorithm are: Property 6. For each prepare or propose message received by an acceptor, the message is processed by the acceptor only if epoch received is greater than or equal to the last promised epoch. Property 7. For each prepare or propose message received, the acceptor’s last promised epoch is set to the epoch received. This is after Property 6 has been satisfied. Property 8. For each prepare message received, the acceptor replies with promise. This is after Properties 6 & 7 have been satisfied. Property 9. For each propose message received, the acceptor replies with accept after updating its last accepted proposal. This is after Properties 6 & 7 have been satisfied. Property 10. Last promised epoch and last accepted proposal are persistent and only updated by Properties 7 & 9 In the following three sections (§2.5, §2.6 & §2.7), we prove that the Classic Paxos algorithm satisfies the requirements of non-triviality, safety and progress and thus is a solution to distributed consensus.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)