PDF Publication Title:
Text from PDF Page: 067
CHAPTER 3. KNOWN REVISIONS 67 Example: Efficient recovery from NACKs Earlier (in §3.1) we learned that negative responses (NACKs) could be used to provide proposers with additional information about the state of the acceptors. In Algorithm 5, the proposer restarted the proposer algorithm if a no-promise(e,f) or no-accept(e,f) was received. We also discussed that the NACKs could also include the last accepted proposal (g,w), for example no-promise(e,f,g,w) or no-accept(e,f,g,w), but at this time this additional information was of no benefit. Proposal copying allows proposers to utilise this information. If a negative response includes a proposal (g, w) that is not nil, then the proposer has learned that epoch g maps to value w. Instead of retrying the proposal from line 1, the proposer may jump to phase two of the proposal (g,w). This is shown in lines 14-16 and 28-30 of algorithm 1114. Furthermore, from negative responses to previous proposals which include the proposal (e, v), the proposer learns that the proposal (e, v) has been accepted by the acceptor thus this acceptor can count towards the phase two quorum (line 24, Algorithm 11). Figure 3.5 shows a revised version of Figure 3.1 where proposer p1 copies the proposal (5, B) and thus skips phase one of epoch 5. For simplicity, this scenario assumes that the no-promise from acceptor a2 is lost or delayed. As usual the proposer sent their requests to all acceptors, however in this case there is no need for proposer p1 to send propose(5,B) to acceptor a1 as p1 already knows that a1 has accepted the proposal (5, B). Example: Efficient recovery on co-located systems Consider a system where proposers and acceptors are co-located on each participant and phase three is used for termination. If a participant has accepted a proposal (e,v) but not learned that a decision has been reached within a timeout, it could start a recovery proposer. Using proposal copying, the participant can skip phase one and proceed to phase two where it sends propose(e,v) to all other participants. Not only may the participant decide the value in only a single phase (phase two) but also there will be no conflict between the original proposer and the copying proposers. In summary to copy the proposal (e, v), a participant first must learn that at some point propose(e,v) had been dispatched. This means that the value v has been chosen to corre- spond with the epoch e. In the next section, we explore what happens if instead values are statically pre-allocated to epochs. 13This is a generalisation of phase two bypass (§3.2). 14Algorithm 11 also includes the requirement that f = g otherwise proposal copying is unlikely to be successful.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 |