License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.DISC.2022.36
URN: urn:nbn:de:0030-drops-172272
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17227/
Go to the corresponding LIPIcs Volume Portal

Hu, Xing ; Toueg, Sam

On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures

pdf-format:
LIPIcs-DISC-2022-36.pdf (0.9 MB)

Abstract

The implementation of registers from (potentially) weaker registers is a classical problem in the theory of distributed computing. Since Lamport’s pioneering work [Leslie Lamport, 1986], this problem has been extensively studied in the context of asynchronous processes with crash failures. In this paper, we investigate this problem in the context of Byzantine process failures, with and without process signatures. In particular, we first show a strong impossibility result, namely, that there is no wait-free linearizable implementation of a 1-writer n-reader register from atomic 1-writer (n-1)-reader registers. In fact, this impossibility result holds even if all the processes except the writer are given atomic 1-writer n-reader registers, and even if we assume that the writer can only crash and at most one reader is subject to Byzantine failures. In light of this impossibility result, we give two register implementations. The first one implements a 1-writer n-reader register from atomic 1-writer 1-reader registers. This implementation is linearizable (under any combination of Byzantine process failures), but it is wait-free only under the assumption that the writer is correct or no reader is Byzantine - thus matching the impossibility result. The second implementation assumes process signatures; it is wait-free and linearizable under any number and combination of Byzantine process failures.

BibTeX - Entry

@InProceedings{hu_et_al:LIPIcs.DISC.2022.36,
  author =	{Hu, Xing and Toueg, Sam},
  title =	{{On Implementing SWMR Registers from SWSR Registers in Systems with Byzantine Failures}},
  booktitle =	{36th International Symposium on Distributed Computing (DISC 2022)},
  pages =	{36:1--36:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-255-6},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{246},
  editor =	{Scheideler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2022/17227},
  URN =		{urn:nbn:de:0030-drops-172272},
  doi =		{10.4230/LIPIcs.DISC.2022.36},
  annote =	{Keywords: distributed computing, concurrency, linearizability, shared registers}
}

Keywords: distributed computing, concurrency, linearizability, shared registers
Collection: 36th International Symposium on Distributed Computing (DISC 2022)
Issue Date: 2022
Date of publication: 17.10.2022

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