PDF Publication Title:
Text from PDF Page: 115
CHAPTER 7. EPOCHS REVISED 115 initially set to nil3. This algorithm is the same as the acceptor algorithm for SAA (2.1.1). As before, the safety proofs still hold as all previous properties still hold. These two simple mechanisms, exclusive epochs from an allocator and a shared epoch from an allocator, allows any proposer to be allocated the minimum epoch, enabling them to bypass phase one. This does, however, require an extra phase to request and receive an epoch. Furthermore, the liveness of the system now also depends on the availability of the allocator, introducing a single point of failure, meaning the algorithms are of little practical use. We will address this limitation later in §7.4. 7.2 Epochs by value mapping The reason for requiring unique epochs is to ensure proposers cannot dispatch propose(e,v) for the same epoch e and different values v. Another mechanism for achieving this is to pre-allocate epochs to their associated value instead of to proposers. A proposer wishing to propose a value v will use its first epoch. If the proposer is unable to choose its own value after executing phase one, it will need to retry phase one with the epoch associated with its expected value. The advantages of this approach are that proposers do not need to store epochs in persistent storage (as is the case for epochs by pre-allocation) or phase one quorum intersection (as is the case for epochs by voting). The result of this is that any proposer who wishes to propose the value corresponding with the minimum epoch emin may skip phase one. However, phase one now requires knowledge of the value to be proposed. This also means that the phase one cannot be pre-executed (as described in §3.5). As such more phases may be needed in situations where the proposer changes the value they wish to propose as an outcome of phase one. This approach does not satisfy the problem of distributed consensus as it can only be applied to systems where the values which may be decided are to be within a finite known set, we will address this limitation later in §7.44. Example: Binary consensus algorithm This approach is best illustrated by considering an algorithm to reach consensus over a binary value, for example on whether a transaction should be committed (v = 1) or aborted (v = 0). Algorithms 22 and 23 give example pseudocode for this. We will let odd epochs correspond to v = 1 and even epochs correspond to v = 0. Since emin = 0, we can utilise skipping phase one (from Paxos revision B) so an abort decision could be achieved in 3This statement assumes that the value is stored in persistent storage. Otherwise, the allocator would need to allocate new epochs on recovery. 4Known infinite value sets can also be supported provided the epoch set is divisible into an infinite number of infinite subsets.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 |