PDF Publication Title:
Text from PDF Page: 089
CHAPTER 4. QUORUM INTERSECTION REVISED 89 two. We can reduce the size (and/or increase the number) of phase two quorums at the cost of increasing the size (and/or reducing the number) of phase one quorums. Multi-Paxos with majority quorums tightly couples performance, system size and fault tolerance. Systems may now choose the most suitable trade-offs for a given scenario. This modification optimises for the steady-state performance, whilst increasing the cost of recovering from failure. One exception to this rule is known as the even nodes optimisation. When the number of acceptors, na is even then the quorum size for Multi-Paxos is na + 1 2 thus existing Multi-Paxos systems recommend against deploying on an even number of acceptors. With Paxos revision A, we can reduce the phase two quorum to na for even na, 2 making deployment on an even number of acceptors a viable option. This improvement to the phase two quorum size has no penalties elsewhere thus is effectively free. The leader learns that a decision has been successfully reached once it receives accepts from a majority of acceptors. If we assume that propose messages are sent to all acceptors, the latency is therefore bounded by the round trip time to the fastest majority of acceptors. By reducing the size of the phase two quorum (and/or increasing the number of quorums), this latency is reduced (or, in the worst case, latency is unchanged). Reducing the decision latency thus increases the throughput which can be achieved under load2. Multi-Paxos is already widely deployed in practice. As such this optimisation to Multi-Paxos, even if marginal, can have wide-reaching impact with minimal implementation effort. As previously discussed (§3.12), it is necessary only for the proposer to send propose messages to a phase two quorum of acceptors, provided the proposer can retry with another phase two quorum if an acceptor does not respond. This approach (almost) halves the number of messages sent per decision during the steady state of Classic Paxos, thus reducing the load on the leader and on the network. By having only the minimum number of acceptors accept each value, the overall storage requirement is also reduced. However, compared to sending propose messages to all acceptors, decision latency is increased both with and without failures. By reducing the size of the phase two quorum (and/or increasing the number of quorums), we can further reduce the number of messages and copies of accepted value. One approach would be to alternate between groups in a set of disjoint quorums. This approach could vastly improve the throughput. This approach also reduces the space re- quirements for storing the sequence and is similar to sharding the sequence. An alternative approach would be to have a leader use a small fixed quorum of acceptors for the phase two. The remaining acceptors would be standbys since they are only needed in the case of failure. 2This is assuming the algorithm has some bound on the number of concurrent decisions and ignores the effects of batching decisions.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)