La puissance de désaccord d'un adversaire

Résumé : Un des résultats fondamentaux de l'algorithmique distribuée est que le niveau d'accord qui peut être obtenu en présence de $t$ pannes est exactement $t+1$. Autrement dit un adversaire qui peut mettre en panne n'importe quel sous ensemble d'au plus $t$ processus peut empêcher les autres processus de se mettre d'accord sur $t$ valeurs. Mais quelle est la puissance des ($2^{2^n} -n$) autres adversaires qui ne peuvent mettre en panne que certaines combinaisons des processus? Cet article présente une caractérisation précise d'un adversaire. On y introduit la notion de "puissance de désaccord". La puissance de désaccord d'un adversaire est le plus grand entier $k$ tel que l'accord des processus sur $k$ valeurs soit possible avec cet adversaire. Puis on montre comment {\em calculer} automatiquement cet entier pour un adversaire donné.
Type de document :
Communication dans un congrès
12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00474206
Contributeur : Carole Delporte-Gallet <>
Soumis le : lundi 19 avril 2010 - 12:37:37
Dernière modification le : jeudi 11 janvier 2018 - 06:17:41
Document(s) archivé(s) le : lundi 22 octobre 2012 - 15:10:14

Fichier

disagreement_power.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00474206, version 1

Collections

Citation

Carole Delporte-Gallet, Hugues Fauconnier, Rachid Guerraoui, Andreas Tielmann. La puissance de désaccord d'un adversaire. 12èmes Rencontres Francophones sur les Aspects Algorithmiques de Télécommunications (AlgoTel), 2010, Belle Dune, France. 2010. 〈inria-00474206〉

Partager

Métriques

Consultations de la notice

72

Téléchargements de fichiers

50