Replacement: Decentralized Failure Handling for Replicated State Machines

We investigate methods for handling failures in a Paxos State Machine and introduce Replacement, a novel approach to handle failures. Replacement is fully decentralized and does not rely on consensus. This allows failed replicas to be replaced quickly, avoiding the bottleneck of a single leader. Instead of handling failures in the order proposed by a leader, concurrent replacements are combined to guarantee that all failed replicas are replaced. Replacement also allows the state machine to process client requests during failure handling, even while disagreeing on the current configuration. As our evaluation shows, this enables Replacement to quickly handle failures, with minimal disruption in the processing of client requests.