Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors

Michel Raynal 1 Julien Stainer 1
1 ASAP - As Scalable As Possible: foundations of large scale dynamic distributed systems
Inria Rennes – Bretagne Atlantique , IRISA-D1 - SYSTÈMES LARGE ÉCHELLE
Résumé : Les modèles de systèmes distribués asynchrones communicant par mémoire partagée sont équivalents, du point de vue de la calculabilité, au modèle itéré où les processus communiquent via une séquence d'objets \emph{write-snapshot}. Cependant, il a été montré que l'utilisation naïve, dans le modèle itéré, des détecteurs de fautes définis pour la mémoire partagée n'apportait aucune puissance de calcul additionelle. Cet article propose une méthode systématique pour porter les détecteurs de fautes du modèle classique communicant par mémoire partagée dans le modèle itéré, ceci en préservant les équivalences de modèles. Dans ce but, il introduit la notion de processus \emph{fortement corrects} qui aide à décrire les possibilités de communication dans le modèle itéré. L'article fournit des simulations génériques (ne dépendant pas ou peu du détecteur de faute) pour prouver les équivalences de modèles. Les cas de plusieurs détecteurs de fautes connus sont traités et le résultat est étendu au cas de la $t$-résilience. Enfin, un algorithme de consensus dans le modèle itéré augmenté du détecteur de faute correspondant à $\Omega$ illustre une des possibilités offertes par cette étude.
Type de document :
Rapport
[Research Report] PI-1991, 2012
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00670154
Contributeur : Julien Stainer <>
Soumis le : mardi 21 février 2012 - 11:18:41
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : mardi 22 mai 2012 - 02:20:46

Fichier

adding-fd-to-iis-v8-rr.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00670154, version 1

Citation

Michel Raynal, Julien Stainer. Increasing the Power of the Iterated Immediate Snapshot Model with Failure Detectors. [Research Report] PI-1991, 2012. 〈hal-00670154〉

Partager

Métriques

Consultations de la notice

941

Téléchargements de fichiers

182