Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH scholarly article en Cohen, Shir; Keidar, Idit https://www.dagstuhl.de/lipics License: Creative Commons Attribution 4.0 license (CC BY 4.0)
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-148203
URL:

;

Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer

pdf-format:


Abstract

We formalize Byzantine linearizability, a correctness condition that specifies whether a concurrent object with a sequential specification is resilient against Byzantine failures. Using this definition, we systematically study Byzantine-tolerant emulations of various objects from registers. We focus on three useful objects- reliable broadcast, atomic snapshot, and asset transfer. We prove that there exist n-process f-resilient Byzantine linearizable implementations of such objects from registers if and only if f < n/2.

BibTeX - Entry

@InProceedings{cohen_et_al:LIPIcs.DISC.2021.18,
  author =	{Cohen, Shir and Keidar, Idit},
  title =	{{Tame the Wild with Byzantine Linearizability: Reliable Broadcast, Snapshots, and Asset Transfer}},
  booktitle =	{35th International Symposium on Distributed Computing (DISC 2021)},
  pages =	{18:1--18:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-210-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{209},
  editor =	{Gilbert, Seth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2021/14820},
  URN =		{urn:nbn:de:0030-drops-148203},
  doi =		{10.4230/LIPIcs.DISC.2021.18},
  annote =	{Keywords: Byzantine linearizability, concurrent algorithms, snapshot, asset transfer}
}

Keywords: Byzantine linearizability, concurrent algorithms, snapshot, asset transfer
Seminar: 35th International Symposium on Distributed Computing (DISC 2021)
Issue date: 2021
Date of publication: 04.10.2021


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