2026-07-30T22:18:28Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19525 2024-03-06T11:04:13Z ddc:004 open_access

Atomic Register Abstractions for Byzantine-Prone Distributed Systems Kowalski, Vincent Mostéfaoui, Achour Perrin, Matthieu Byzantine processes Concurrent Object Linearizability Shared Register 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Vincent Kowalski and Achour Mostéfaoui and Matthieu Perrin 2024 Is Part Of LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2023.35 urn:nbn:de:0030-drops-195257 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.35 eng https://creativecommons.org/licenses/by/4.0/legalcode