License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2020.24
URN: urn:nbn:de:0030-drops-131024
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13102/
Go to the corresponding LIPIcs Volume Portal

França Rezende, Tuanir ; Sutra, Pierre

Leaderless State-Machine Replication: Specification, Properties, Limits

pdf-format:
LIPIcs-DISC-2020-24.pdf (0.6 MB)

Abstract

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.

BibTeX - Entry

@InProceedings{franarezende_et_al:LIPIcs:2020:13102,
  author =	{Tuanir Fran{\c{c}}a Rezende and Pierre Sutra},
  title =	{{Leaderless State-Machine Replication: Specification, Properties, Limits}},
  booktitle =	{34th International Symposium on Distributed Computing (DISC 2020)},
  pages =	{24:1--24:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-168-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{179},
  editor =	{Hagit Attiya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/13102},
  URN =		{urn:nbn:de:0030-drops-131024},
  doi =		{10.4230/LIPIcs.DISC.2020.24},
  annote =	{Keywords: Fault Tolerance, State Machine Replication, Consensus}
}

Keywords: Fault Tolerance, State Machine Replication, Consensus
Collection: 34th International Symposium on Distributed Computing (DISC 2020)
Issue Date: 2020
Date of publication: 07.10.2020

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI