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

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.
Type de document :
Article dans une revue
Computing, Springer Verlag, 2018, pp.1-16. 〈10.1007/s00607-018-0615-8〉
Liste complète des métadonnées

Littérature citée [16 références]  Voir  Masquer  Télécharger

https://hal.laas.fr/hal-01784210
Contributeur : Matthieu Roy <>
Soumis le : jeudi 3 mai 2018 - 10:32:17
Dernière modification le : mardi 11 septembre 2018 - 15:19:11

Fichier

computing-2018-author.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Citation

Achour Mostefaoui, Michel Raynal, Matthieu Roy. Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems. Computing, Springer Verlag, 2018, pp.1-16. 〈10.1007/s00607-018-0615-8〉. 〈hal-01784210〉

Partager

Métriques

Consultations de la notice

379

Téléchargements de fichiers

43