La puissance de désaccord d'un adversaire - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2010

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é.
Fichier principal
Vignette du fichier
disagreement_power.pdf (56.13 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00474206 , version 1 (19-04-2010)

Identifiants

  • HAL Id : inria-00474206 , version 1

Citer

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), Maria Gradinariu Potop-Butucaru et Hervé Rivano, 2010, Belle Dune, France. ⟨inria-00474206⟩
91 Consultations
62 Téléchargements

Partager

Gmail Facebook X LinkedIn More