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.ICDT.2020.17
URN: urn:nbn:de:0030-drops-119418
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11941/
Go to the corresponding LIPIcs Volume Portal

Hellings, Jelle ; Sadoghi, Mohammad

Coordination-Free Byzantine Replication with Minimal Communication Costs

pdf-format:
LIPIcs-ICDT-2020-17.pdf (0.7 MB)

Abstract

State-of-the-art fault-tolerant and federated data management systems rely on fully-replicated designs in which all participants have equivalent roles. Consequently, these systems have only limited scalability and are ill-suited for high-performance data management. As an alternative, we propose a hierarchical design in which a Byzantine cluster manages data, while an arbitrary number of learners can reliable learn these updates and use the corresponding data.
To realize our design, we propose the delayed-replication algorithm, an efficient solution to the Byzantine learner problem that is central to our design. The delayed-replication algorithm is coordination-free, scalable, and has minimal communication cost for all participants involved. In doing so, the delayed-broadcast algorithm opens the door to new high-performance fault-tolerant and federated data management systems. To illustrate this, we show that the delayed-replication algorithm is not only useful to support specialized learners, but can also be used to reduce the overall communication cost of permissioned blockchains and to improve their storage scalability.

BibTeX - Entry

@InProceedings{hellings_et_al:LIPIcs:2020:11941,
  author =	{Jelle Hellings and Mohammad Sadoghi},
  title =	{{Coordination-Free Byzantine Replication with Minimal Communication Costs}},
  booktitle =	{23rd International Conference on Database Theory (ICDT 2020)},
  pages =	{17:1--17:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-139-9},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{155},
  editor =	{Carsten Lutz and Jean Christoph Jung},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/11941},
  URN =		{urn:nbn:de:0030-drops-119418},
  doi =		{10.4230/LIPIcs.ICDT.2020.17},
  annote =	{Keywords: Byzantine learner, coordination-free checkpoint protocol, delayed-replication, information dispersal, consensus}
}

Keywords: Byzantine learner, coordination-free checkpoint protocol, delayed-replication, information dispersal, consensus
Collection: 23rd International Conference on Database Theory (ICDT 2020)
Issue Date: 2020
Date of publication: 11.03.2020
Supplementary Material: Video of the Presentation: https://doi.org/10.5446/46834

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