PDF Publication Title:
Text from PDF Page: 114
114 7.1. EPOCHS FROM AN ALLOCATOR 7.1 Epochs from an allocator Thus far we have assumed that the epochs, E, have been allocated a priori between proposers. Instead, we could use an allocator to dynamically allocate epochs between proposers. The allocator need be no more complex than a simple counter, starting at emin. We replace the selection of the next epoch (Lines 3-4 in Algorithm 3) with a message exchange with the allocator. The allocator must guarantee that each epoch is allocated at most once1. Algorithm 21: Allocator algorithm state : 1 2 3 4 5 6 • sid: sequence number • vid: service version number (persistent, initially 0) sid←0,vid←vid+1 while true do switch do case generate-next() received from proposer sid ← sid + 1 send allocate(( vid,sid)) to proposer Algorithm 21 gives a na ̈ıve algorithm to implement the allocator on a single participant. Epochs are an ordered tuples of the form (vid, sid) such as: E = {(1,1),(1,2),(1,3),...,(2,1),(2,2),(2,3),...} The algorithm is effectively a simple counter, sid, with a version number, vid, to ensure uniqueness of epochs assigned in the case of failure. The service version number, vid, is stored in persistent storage and incremented on each restart. The sequence number, sid, is stored in volatile storage and incremented on each allocation.2 Given that an allocator will assign each epoch at most once and will assign epochs in increasing order, our safety proofs still hold without revisions as all previous properties still hold. We could extend this na ̈ıve approach to have proposers include their candidate value in their request to the allocator. The allocator could store the epoch to value mapping. This would enable the allocator to re-allocate epochs to other proposers on the condition that they propose the same value as was originally assigned. This could allow for conflict-free recovery for slow/failed proposers. In this case, emin would be the only epoch allocated by the allocator. The allocator would equivalent to a single write-once register, which is 1Note that allocation need not be in-order nor does every epoch need to be allocated for safety. However, similar to Classic Paxos, using epochs in-order does simplify our proof of progress. 2This algorithm implements unique epochs without synchronous writes to persistent storage for each proposal, this technique was first described in §3.8.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)