Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems

Achour Mostéfaoui 1 Michel Raynal 2, *
* Corresponding author
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
IRISA-D1 - SYSTÈMES LARGE ÉCHELLE, Inria Rennes – Bretagne Atlantique
Abstract : Atomic registers are certainly the most basic objects of computing science. Their implementation on top of an n-process asynchronous message-passing system has received a lot of attention. It has been shown that t < n/2 (where t is the maximal number of processes that may crash) is a necessary and sufficient requirement to build an atomic register on top of a crash-prone asynchronous message-passing system. Considering such a context, this paper presents an algorithm which implements a single-writer multi-reader atomic register with four message types only, and where no message needs to carry control information in addition to its type. Hence, two bits are sufficient to capture all the control information carried by all the implementation messages. Moreover, the messages of two types need to carry a data value while the messages of the two other types carry no value at all. As far as we know, this algorithm is the first with such an optimality property on the size of control information carried by messages. It is also particularly efficient from a time complexity point of view.
Complete list of metadata

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-01271135
Contributor : Michel Raynal <>
Submitted on : Monday, February 8, 2016 - 6:09:51 PM
Last modification on : Thursday, January 7, 2021 - 4:26:02 PM
Long-term archiving on: : Saturday, November 12, 2016 - 2:39:22 PM

Files

Counter-free-msgs-V7.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01271135, version 1
  • ARXIV : 1602.02695

Citation

Achour Mostéfaoui, Michel Raynal. Two-Bit Messages are Sufficient to Implement Atomic Read/Write Registers in Crash-prone Systems. 2016. ⟨hal-01271135⟩

Share

Metrics

Record views

1285

Files downloads

321