Skip to Main content Skip to Navigation
Conference papers

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é.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00474206
Contributor : Carole Delporte-Gallet <>
Submitted on : Monday, April 19, 2010 - 12:37:37 PM
Last modification on : Saturday, March 28, 2020 - 2:14:30 AM
Long-term archiving on: : Monday, October 22, 2012 - 3:10:14 PM

File

disagreement_power.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00474206, version 1

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

Share

Metrics

Record views

175

Files downloads

97