PDF Publication Title:
Text from PDF Page: 059
CHAPTER 3. KNOWN REVISIONS 59 Paxos. From the Safety of future proposals (Theorem 13), if a decision has been reached, the value chosen by the value selection rules will be the decided value. Most consensus algorithms utilise some form of termination. Mencius [MJM08] and Ring Paxos [MPSP10, §4] use explicit phase three messages (called learn and decision respec- tively). Whereas algorithms such as Raft and VRR [LC12, §4.1] use a commit index in future messages instead of an explicit phase three to notify acceptors that a decision has been reached. Once an acceptor learns that a proposal has been decided, it is safe for this information to be shared with other participants including acceptors [MJM08, §4.5]. 3.4 Distinguished proposer In Figure 2.6 (§2.3), we observed the issue of duelling proposers where multiple proposers conflict over the proposal to be decided. This problem of duelling proposers is why our proof of progress (§2.7) assumed that exactly one proposer was executing Classic Paxos. In practice, algorithms can minimise the likelihood of duelling proposers by designating one proposer as the distinguished. By modifying the proposer algorithm of non-distinguished proposer to forward candidate values to this proposer, the distinguished proposer becomes a point of serialisation, minimising the chance of duelling6. This mechanism improves reliability of performance by making it more likely that exactly one proposer is executing Classic Paxos at a given time. If the distinguished proposer appears to be slow or unresponsive, another proposer can become a distinguished proposer and thus propose values directly. It is always safe for there be to no distinguished proposer, multiple distinguished proposers or inconsistent knowledge of the distinguished proposer7. However to guarantee progress, there should be exactly one distinguished proposer at a given time and all proposers should be aware of its identity. To satisfy this condition, we require reliable failure detection, which is not possible in an asynchronous distributed system [FLP85]. Instead we can approximate reliable failure detectors with heartbeats and timeouts, this does however require us to strengthen the liveness conditions for progress to bound message delay, clock drift and operating speed between proposers. The weakest liveness conditions for failure detection are studied elsewhere in the literature [CHT96, MOZ05]. This optimisation, known as the distinguished proposer, is widely utilised [Lam01a, §2.4][LC12, 6In practice, candidate values often originate from external clients who can try to send values directly to the distinguished proposer. Examples of algorithms which take this approach include VRR [LC12, §4] and Raft [OO14, §8]. Alternatively, clients can broadcast values to all proposers, an approach taken by Moderately Complex Paxos [VRA15, §2.1] 7In other words, choosing a distinguished proposer is not a leader election problem and does not itself require distributed consensusPDF 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 |