One Acceptor is Enough
The celebrated Paxos protocol implements a reliable service as a state machine replicated over several machines. Replication provides reliability against permanent failures and availability against temporary crash failures. Whereas, in theory, Paxos can tolerate any number f of crash failures using 2f + 1 replicas, in practice, it is often appealing to use it in order to tolerate a single failure using three replicas for the probability of two simultaneous failures is sometimes considered low enough. We show in this paper how, in this particular case of three replicas, we can increase the throughput of Multi-Paxos, which is an efficient variation of Paxos used in deployed systems [4, 2], by a factor of 2 by using a new protocol we call OneAcceptor. In short, OneAcceptor changes Multi-Paxos to use only a single acceptor role and to switch it with another acceptor in the case of failure. The number of exchanged messages between replicas reduces considerably, without trading, however, neither the consistency nor the availability of Multi-Paxos.