H.: Asynchronous Reconfiguration for Paxos State Machines

Abstract. This paper addresses reconfiguration of a Replicated State Machine (RSM) in an asynchronous system. It is well known that consen-sus cannot be solved in an asynchronous system. Therefore an RSM pro-viding strong consistency, cannot guarantee progress in an asynchronous system. However, we show that reconfiguring the RSM is possible in a purely asynchronous system. This differs from all existing reconfiguration methods which rely on consensus to choose a new configuration. Since a reconfiguration to a new set of machines or even a different datacenter can serve to restore synchrony between replicas, asynchronous reconfig-uration can also serve to increase the availability of an RSM.