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

Achour Mostefaoui 1 Michel Raynal 2, *
* Auteur correspondant
2 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : The atomic register is certainly the most basic object of computing science. Its 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 visits the notion of a fast implementation of an atomic register, and presents a new time-efficient asynchronous algorithm. Its time-efficiency is measured according to two different underlying synchrony assumptions. Whatever this assumption, a write operation always costs a round-trip delay, while a read operation costs always 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 one of the famous ABD algorithm (proposed by Attiya, Bar-Noy, and Dolev).
Type de document :
[Research Report] IRISA. 2016, pp.14
Liste complète des métadonnées

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

Contributeur : Michel Raynal <>
Soumis le : vendredi 15 janvier 2016 - 13:51:10
Dernière modification le : jeudi 15 novembre 2018 - 11:57:36
Document(s) archivé(s) le : samedi 16 avril 2016 - 10:12:58


Fichiers produits par l'(les) auteur(s)


  • HAL Id : hal-01256067, version 1
  • ARXIV : 1601.04820


Achour Mostefaoui, Michel Raynal. Time-Efficient Read/Write Register in Crash-prone Asynchronous Message-Passing Systems. [Research Report] IRISA. 2016, pp.14. 〈hal-01256067〉



Consultations de la notice


Téléchargements de fichiers