High-Throughput Multi-Leader Paxos Consensus with Insanely Scalable SMR
Gabriel Momm Buzzi, Odorico Machado Mendizabal · 2025
Distributed consensus protocols are essential building blocks for the development of distributed systems. They facilitate critical functionalities such as coordination in mutual exclusion and election algorithms, ensuring total order delivery in broadcast communication, and enabling active replication in approaches like State Machine Replication (SMR). Paxos has emerged as the most prominent distributed consensus algorithm, inspiring numerous optimizations over the past decades. In particular, some enhancements focus on improving Paxos’s throughput and scalability by addressing its single-leader bottleneck through multi-leader and leaderless variants. This paper examines key optimizations related to quorum sizes, reconfiguration, message exchange overhead, and the decentralization of the leader role, with an emphasis on multi-leader and leaderless approaches. Additionally, we develop a high-throughput multi-leader Paxos implementation using the ISS (Insanely Scalable SMR) framework. We benchmark this implementation against other multi-leader and leaderless protocols, including WPaxos and EPaxos. Experimental results demonstrate that the proposed implementation achieves nearly twice the throughput of WPaxos and EPaxos, albeit with increased latency due to ISS bucket rotation overheads.