Skip to Main content Skip to Navigation
Journal articles

Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems

Achour Mostefaoui 1 Michel Raynal 2 Matthieu Roy 3, * 
* Corresponding author
2 WIDE - the World Is Distributed Exploring the tension between scale and coordination
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
3 LAAS-TSF - Équipe Tolérance aux fautes et Sûreté de Fonctionnement informatique
LAAS - Laboratoire d'analyse et d'architecture des systèmes
Abstract : The atomic register is one of the most basic and useful object of computing science, and its simple read-write semantics is appealing when programming distributed systems. Hence, its implementation on top of crash-prone asynchronous message-passing systems has received a lot of attention. It was shown that having a strict minority 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. This paper visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm that reduces latency in many cases: a write operation always costs a round-trip delay, while a read operation costs a round-trip delay in favorable circumstances (intuitively, when it is not concurrent with a write). When designing this algorithm, the design spirit was to be as close as possible to the original algorithm proposed by Attiya, Bar-Noy, and Dolev.
Complete list of metadata

Cited literature [16 references]  Display  Hide  Download
Contributor : Matthieu Roy Connect in order to contact the contributor
Submitted on : Thursday, May 3, 2018 - 10:32:17 AM
Last modification on : Friday, August 5, 2022 - 2:54:51 PM
Long-term archiving on: : Tuesday, September 25, 2018 - 2:02:44 PM


Files produced by the author(s)



Achour Mostefaoui, Michel Raynal, Matthieu Roy. Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems. Computing, Springer Verlag, 2019, 101 (1), pp.3-17. ⟨10.1007/s00607-018-0615-8⟩. ⟨hal-01784210⟩



Record views


Files downloads