2026-08-06T10:24:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13102 2024-03-06T10:51:34Z ddc:004 open_access

Leaderless State-Machine Replication: Specification, Properties, Limits França Rezende, Tuanir Sutra, Pierre Fault Tolerance State Machine Replication Consensus Modern Internet services commonly replicate critical data across several geographical locations using state-machine replication (SMR). Due to their reliance on a leader replica, classical SMR protocols offer limited scalability and availability in this setting. To solve this problem, recent protocols follow instead a leaderless approach, in which each replica is able to make progress using a quorum of its peers. In this paper, we study this new emerging class of SMR protocols and states some of their limits. We first propose a framework that captures the essence of leaderless state-machine replication (Leaderless SMR). Then, we introduce a set of desirable properties for these protocols: (R)eliability, (O)ptimal (L)atency and (L)oad Balancing. We show that protocols matching all of the ROLL properties are subject to a trade-off between performance and reliability. We also establish a lower bound on the message delay to execute a command in protocols optimal for the ROLL properties. This lower bound explains the persistent chaining effect observed in experimental results. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tuanir França Rezende and Pierre Sutra 2020 Is Part Of LIPIcs, Volume 179, 34th International Symposium on Distributed Computing (DISC 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2020.24 urn:nbn:de:0030-drops-131024 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2020.24 eng https://creativecommons.org/licenses/by/3.0/legalcode