Search Results

Documents authored by Kowalski, Vincent


Document
Atomic Register Abstractions for Byzantine-Prone Distributed Systems

Authors: Vincent Kowalski, Achour Mostéfaoui, and Matthieu Perrin

Published in: LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023)


Abstract
The construction of the atomic register abstraction over crash-prone asynchronous message-passing systems has been extensively studied since the founding work of Attiya, Bar-Noy, and Dolev. It has been shown that t < n/2 (where t is the maximal number of processes that may be faulty) is a necessary and sufficient requirement to build an atomic register. However, little attention has been paid to systems where faulty processes may exhibit a Byzantine behavior. This paper studies three definitions of linearizable single-writer multi-reader registers encountered in the state of the art: Read/Write registers whose read perations return the last written value, Read/Write-Increment registers whose read perations return both the last written value and the number of previously written values, and Read/Append registers whose read perations return the sequence of all previously written values. More specifically, it compares their computing power and the necessary and sufficient conditions on the maximum ratio t/n which makes it possible to build reductions from one register to another. Namely, we prove that t < n/3 is necessary and sufficient to implement a Read/Write-Increment register from Read/Write registers whereas this bound is only t < n/2 for a reduction from a Read/Append register to Read/Write-Increment registers. Reduction algorithms meeting these bounds are also provided.

Cite as

Vincent Kowalski, Achour Mostéfaoui, and Matthieu Perrin. Atomic Register Abstractions for Byzantine-Prone Distributed Systems. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 286, pp. 35:1-35:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)


Copy BibTex To Clipboard

@InProceedings{kowalski_et_al:LIPIcs.OPODIS.2023.35,
  author =	{Kowalski, Vincent and Most\'{e}faoui, Achour and Perrin, Matthieu},
  title =	{{Atomic Register Abstractions for Byzantine-Prone Distributed Systems}},
  booktitle =	{27th International Conference on Principles of Distributed Systems (OPODIS 2023)},
  pages =	{35:1--35:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-308-9},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{286},
  editor =	{Bessani, Alysson and D\'{e}fago, Xavier and Nakamura, Junya and Wada, Koichi and Yamauchi, Yukiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.35},
  URN =		{urn:nbn:de:0030-drops-195257},
  doi =		{10.4230/LIPIcs.OPODIS.2023.35},
  annote =	{Keywords: Byzantine processes, Concurrent Object, Linearizability, Shared Register}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail