The weakest failure detector to implement a register in asynchronous systems with hybrid communication

Damien Imbs 1 Michel Raynal 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Abstract : This paper introduces an asynchronous crash-prone hybrid system model. The system is hybrid in the way the processes can communicate. On the one side, a process can send messages to any other process. On another side, the processes are partitioned into clusters and each cluster has its own read/write shared memory. In addition to the model, a main contribution of the paper concerns the implementation of an atomic register in this system model. More precisely, a new failure detector (denoted MΣ) is introduced and it is shown that, when considering the information on failures needed to implement a register, this failure detector is the weakest. To that end, the paper presents an MΣ-based algorithm that builds a register in the considered hybrid system model and shows that it is possible to extract MΣ from any failure detector-based algorithm that implements a register in this model. The paper also (a) shows that MΣ is strictly weaker than Σ (which is the weakest failure detector to implement a register in a classical message-passing system) and (b) presents a necessary and sufficient condition to implement MΣ in a hybrid communication system.
Type de document :
Rapport
[Research Report] PI-1972, 2011, pp.11
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00583155
Contributeur : Ist Rennes <>
Soumis le : mardi 5 avril 2011 - 08:54:19
Dernière modification le : mardi 16 janvier 2018 - 15:54:13
Document(s) archivé(s) le : jeudi 8 novembre 2012 - 13:26:03

Fichier

PI-1972.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00583155, version 1

Citation

Damien Imbs, Michel Raynal. The weakest failure detector to implement a register in asynchronous systems with hybrid communication. [Research Report] PI-1972, 2011, pp.11. 〈inria-00583155〉

Partager

Métriques

Consultations de la notice

315

Téléchargements de fichiers

223