2026-07-26T02:44:07Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25195 2026-01-07T12:38:34Z ddc:004 open_access

Making Democracy Work: Fixing and Simplifying Egalitarian Paxos Ryabinin, Fedor Gotsman, Alexey Sutra, Pierre Consensus state-machine replication fault tolerance Classical state-machine replication protocols, such as Paxos, rely on a distinguished leader process to order commands. Unfortunately, this approach makes the leader a single point of failure and increases the latency for clients that are not co-located with it. As a response to these drawbacks, Egalitarian Paxos [Iulian Moraru et al., 2013] introduced an alternative, leaderless approach, that allows replicas to order commands collaboratively. Not relying on a single leader allows the protocol to maintain non-zero throughput with up to f crashes of any processes out of a total of n = 2f+1. The protocol furthermore allows any process to execute a command c fast, in 2 message delays, provided no more than e = ⌈(f+1)/2⌉ other processes fail, and all concurrently submitted commands commute with c; the latter condition is often satisfied in practical systems. Egalitarian Paxos has served as a foundation for many other replication protocols. But unfortunately, the protocol is very complex, ambiguously specified and suffers from nontrivial bugs. In this paper, we present EPaxos* - a simpler and correct variant of Egalitarian Paxos. Our key technical contribution is a simpler failure-recovery algorithm, which we have rigorously proved correct. Our protocol also generalizes Egalitarian Paxos to cover the whole spectrum of failure thresholds f and e such that n ≥ max{2e+f-1, 2f+1} - the number of processes that we show to be optimal. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Fedor Ryabinin and Alexey Gotsman and Pierre Sutra 2026 Is Part Of LIPIcs, Volume 361, 29th International Conference on Principles of Distributed Systems (OPODIS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2025.22 urn:nbn:de:0030-drops-251955 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2025.22 eng https://creativecommons.org/licenses/by/4.0/legalcode