PDF Publication Title:
Text from PDF Page: 029
CHAPTER 2. CONSENSUS & CLASSIC PAXOS 29 2. Each acceptor receives a propose(e,v). If e is the first epoch promised or if e is equal to or greater than the last promised epoch, then the promised epoch and accepted proposal is updated and the acceptor replies with accept(e). 3. Once the proposer receives accept(e) from the majority of acceptors, it learns that the value v is decided. 4. Otherwise if the proposer times out, it will retry phase 1 with a greater epoch. Phase 1 Phase 2 Message prepare(e) promise(e,f,v) Description e: epoch e: epoch f: last accepted epoch* v: last accepted value* *maybe nil e: epoch v: proposal value e: epoch Sent by: Received by: proposers acceptors acceptors proposers proposers acceptors propose(e,v) accept(e) acceptors proposers Table 2.2: Messages exchanged in Classic Paxos For reference, Table 2.2 gives an overview of the four messages used in Classic Paxos11. We will now look at this process in more detail. 2.2.1 Proposer algorithm Algorithm 3 describes the Classic Paxos algorithm for participants with the role of a proposer. The key input to this algorithm is a candidate value γ to propose and the output is the decided value v. The decided value may or may not be the same as the candidate value, depending upon the state of acceptors when the algorithm is executed. The proposer will only propose its candidate value γ if it is sure that another value has not already been chosen. Once the proposer learns that a value has been decided, no proposer will learn that a different value has been decided. After initialising its variables (Algorithm 3, lines 1-2), the algorithm begins by selecting a epoch e to use (Algorithm 3, line 3). To remain general, we do not specify how the set of available epochs, E ⊆ E, should be generated. However, the algorithm does require that each proposer is configured with an infinite disjoint set of epochs. The algorithm ensures that each epoch is used only once, by removing the current epoch, e, from the set 11These message are often referred to as 1a, 1b, 2a and 2b respectively. Confusingly, the propose message is called prepare in VRR [LC12, §4.1]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)