The Paxos algorithm requires a single correct coordinator process to operate. After a failure, the replacement of the coordinator may lead to a temporary unavailability of the application implemented atop Paxos. So far, this unavailability has been addressed by reducing the coordinator replacement rate through the use of stable coordinator selection algorithms. We have observed that the cost of recovery of the newly elected coordinator's state is at the core of this unavailability problem. In this paper we present a new technique to manage coordinator replacement that allows the recovery to occur concurrently with new consensus rounds. Experimental results show that our seamless approach effectively solves the temporary unavailability problem, its adoption entails uninterrupted execution of the application. Our solution removes the restriction that the occurrence of coordinator replacements is something to be avoided, allowing the decoupling of the application execution from the accuracy of the mechanism used to choose a coordinator. This result increases the performance of the application even in the presence of failures, it is of special importance to the autonomous operation of replicated applications that have to adapt to varying network conditions and partial failures.
A similar strategy of splitting the coordinator role among many processes was taken in Mencius @cite_3 , to minimize the number of exchanged messages in a wide-area network. In Mencius processes take turns running a coordinator and proposers only exchange messages with the closest coordinator. The handover of coordinator responsibilities to another process is a built-in feature of the Mencius protocol. Every instance has a predefined coordinator, that proposes and decides a value in it or decides a special value (no-op) indicating it yields its turn. In Mencius coordinator replacement occurs on a per-instance basis. This effectively solves the temporary unavailability problem, as the state to be transferred is reduced to one instance. However, in the case of a permanent failure of a process, an unbounded number of these simple coordinator replacements will happen continuously for as long as the failed process remains down.
@cite_3
1814543774
We present a protocol for general state machine replication - a method that provides strong consistency - that has high performance in a wide-area network. In particular, our protocol Mencius has high throughput under high client load and low latency under low client load even under changing wide-area network environment and client load. We develop our protocol as a derivation from the well-known protocol Paxos. Such a development can be changed or further refined to take advantage of specific network or application requirements.