Simultaneous Consensus vs Set Agreement a Message-Passing Sensitive Hierarchy of Agreement Problems

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é : Ce rapport etudie les liens entre les problèmes du consensus s-simultané et de l'accord k-ensembliste. Il commence par définir le problème (s, k)-SSA qui généralise les deux problèmes précédents. Le rapport intro- duit ensuite un nouveau détecteur de fautes, noté Zs,k , formé de deux composantes, l'une chargé de rendre possible l'implémentation d'une forme d'"objet mémoire partagée" permettant aux processus de coopérer, tandis que la sec- onde fournit la vivacité nécessaire à un algorithme de (s, k)-SSA. Une particularité de ce détecteur de fautes réside dans le fait que les définitions de ces deux composantes sont intimement liées. Le rapport présente un algorithme basé sur Zs,k qui résoud le problème (s, k)-SSA et prouve que la partie orientée "mémoire partagée" de Zs,k est nécessaire pour le résoudre Enfin, le rapport étudie la structure de la famille des problèmes (s, k)-SSA et montre entre autres que pour s, k > 1, (a) le problème (sk, 1)-SSA est strictement plus difficile que le problème (s, k)-SSA, lui-même strictement plus difficile que le problème (1, ks)-SSA et (b) il existe des paires (s1 , k1 ) et (s2 , k2 ) avec s1 k1 = s2 k2 telles que les problèmes (s1 , k1 )-SSA et (s2 , k2 )-SSA sont incomparables.
Type de document :
Rapport
[Research Report] PI-2003, 2013
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00787992
Contributeur : Julien Stainer <>
Soumis le : vendredi 22 février 2013 - 18:17:50
Dernière modification le : mercredi 16 mai 2018 - 11:23:13
Document(s) archivé(s) le : dimanche 2 avril 2017 - 04:32:25

Fichier

Looking-for-weakest-FD-for-xy-...
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00787992, version 2

Citation

Michel Raynal, Julien Stainer. Simultaneous Consensus vs Set Agreement a Message-Passing Sensitive Hierarchy of Agreement Problems. [Research Report] PI-2003, 2013. 〈hal-00787992v2〉

Partager

Métriques

Consultations de la notice

880

Téléchargements de fichiers

168