PDF Publication Title:
Text from PDF Page: 023
CHAPTER 2. CONSENSUS & CLASSIC PAXOS 23 • Acceptor - A participant who agrees and persists decided values. In a system U of n participants, we will denote the set acceptors as A = {a1,a2,...} whereA⊆U and|A|=na andthesetofproposersasP ={p1,p2,...}whereP ⊆U and |P| = np. A consensus algorithm defines the process by which a value v is chosen by the acceptors from the proposers. We refer to the point in time when the acceptors have committed to a particular value as the commit point. After this point in time, v has been decided and cannot be subsequently altered. The proposers learn which value has been decided, this must always take place after the commit point has been reached. If we are able to reach agreement over a single value, we are able to reach agreement over an infinite sequence of values v1, v2, v3, . . . 3 by independently reaching consensus over each value in the sequence in turn. This sequence could represent updates to a re-writeable register, operations for a replicated state machine, messages for atomic broadcast, a shared log or state changes in a primary-backup system. All notation introduced in this section and the remainder of the thesis is summarised for reference in Table 2.1. 2.1.1 Single acceptor algorithm In the section, we introduce a straw-man algorithm which solves distributed consensus. The algorithm, which we will refer to as the single acceptor algorithm (SAA), requires that exactly one participant be assigned the role of acceptor4. The liveness conditions for SAA are that the acceptor and at least one proposer are up and can exchange messages reliably. This algorithm is included here to familiarise the reader with the terminology and methodology before we progress to more advanced algorithms. The single acceptor algorithm chooses the first value proposed by the proposers. A proposer who has a candidate value γ will propose the value to the acceptor using the message propose(γ). If this is the first proposal the acceptor has received, it will write γ to persistent storage (known as accepting) and notify the proposer that the value has been decided using the message accept(γ). Otherwise, if this is not the first proposal to be received, the acceptor will reply to the proposer with the already decided value γ′ using accept(γ′). In either case, provided that the acceptor is available then the proposer will learn the decided value. See algorithm 1 and algorithm 2 for pseudocode descriptions of this approach5. 3The sequence of values will always be 1-indexed. 4We are not the first to use this straw-man solution to explain the problem of consensus [Lam01a, §2.2] 5Note that for all pseudocode in this thesis, variables are stored in volatile memory and are initially nil unless otherwise stated. Also note that all pseudocode in this thesis favours clarity and consistency over performance.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 | RSS | AMP |