One Acceptor is Enough

Maysam Yabandeh, Leandro R. Franco, Rachid GuerraouiInfoscience 2010

Abstract

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 by a factor of nearly 3 using a new protocol called OneAcceptor. OneAcceptor changes Multi-Paxos to use only a single active 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 consistency or availability.

The Bottleneck in Distributed Consensus

Distributed consensus is the backbone of reliable systems like Google's Chubby or Apache ZooKeeper. Paxos is the foundational algorithm for this task. To tolerate $f$ failures, Paxos typically requires $2f+1$ replicas. In the most common deployment scenario ($f=1$), three servers are used.

In a "collapsed" implementation where every server plays all roles (Proposer, Acceptor, and Learner), the leader (Proposer) often becomes a massive network bottleneck. For every client command, the leader must send messages to and receive replies from a majority of acceptors. This "chatter" consumes the leader's network bandwidth, limiting the total system throughput.

Standard Multi-Paxos message flow showing the high communication overhead between roles.

The OneAcceptor Approach

The authors introduce OneAcceptor, a variation of Multi-Paxos optimized specifically for three-node deployments. The core insight is that while multiple acceptors are needed for availability (to survive a crash), they do not all need to be involved in every single consensus decision for safety.

The Active Acceptor Concept

Unlike standard Multi-Paxos where all replicas act as acceptors for every request, OneAcceptor designates only one Active Acceptor. The leader communicates exclusively with this single node during normal operation. By reducing the leader's message count from 6 (in standard 3-node Multi-Paxos) to 3, the leader can utilize the saved bandwidth to handle more client requests.

The Switch Mechanism

If the Active Acceptor fails, the system must transition to a backup. OneAcceptor uses a separate, low-frequency consensus instance called PaxosUtility to agree on a new backup acceptor. This mechanism ensures that even if the primary acceptor dies, the system can safely resume operations with a new node.

The OneAcceptor switch mechanism triggered by an acceptor failure.

Eliminating Disk Writes

Standard Paxos requires acceptors to log state to persistent storage before responding, which introduces significant latency. OneAcceptor keeps acceptor state in RAM. If a node reboots and loses its memory, the system treats it as a failure and triggers the switch mechanism. A "freshness" flag ($IamFresh$) is used to detect these silent reboots and prevent stale nodes from participating incorrectly.

Performance Evaluation

The protocol was implemented using the Mace framework and evaluated against a standard Multi-Paxos implementation on a cluster of three Xeon servers.

  • Throughput: In error-free scenarios, OneAcceptor achieved a throughput of 8,120 proposals/sec, compared to 2,817 proposals/sec for Multi-Paxos—a 2.88x improvement.
  • Latency: Commit latency remained virtually identical (~105ms). The optimization increases the system's capacity without making individual requests slower.
  • Failure Recovery: When the active acceptor failed, recovery took between 208ms and 261ms. While slower than standard Multi-Paxos (which doesn't require an explicit role switch), this sub-second delay is negligible for most practical applications compared to the massive gains in peak performance.

Conclusion

OneAcceptor demonstrates that "doing less" can lead to significant performance gains in distributed systems. By optimizing for the common case of a healthy three-node cluster and moving the complexity of redundancy to a rare failure-handling path, OneAcceptor nearly triples the throughput of standard Multi-Paxos without sacrificing the core guarantees of consistency and availability.

Summary updated

Abstract

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.
BibTeX
@inproceedings{yabandeh2010one,
  author = {Maysam Yabandeh and Leandro R. Franco and Rachid Guerraoui},
  title = {{One Acceptor is Enough}},
  booktitle = {Infoscience},
  year = {2010},
}
Figure