Skip to Main content Skip to Navigation
Reports

Complexité de l'élection

Christian Lavault 1
1 MODEL - Modeling Random Systems
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, INRIA Rennes
Résumé : L'élection sur les anneaux a déjà donné lieu à quantités de recherches, tant dans le cas où les processus sont tous distingués par leurs identités "anneaux avec identités" que dans celui ou ils sont sans identités, indiscernables "anneaux anonymes". On sait également différencier les classes d'anneaux selon des critères pertinents du point de vue de la complexite en communication des algorithmes, i.e. anneaux synchrones ou asynchrones, uni- ou bidirectionnels, mais aussi anneaux avec ou sans information structurelle "sens général de la direction", connaissance exacte ou approchée de la taille de l'anneau, etc.) : tout types de connaissance à même d'améliorer considérablement la complexité en communication de bien des algorithmes distribués. Cette synthèse tente de montrer que presque tous les problèmes fondamentaux se posant en algorithmique distribuée apparaissent déjà clairement dans le simple cas de l'élection sur des anneaux, et ce, tout particulièrement en ce qui concerne les performances des algorithmes distribués. Elle constitue également une tentative pour faire le point sur les diverses méthodes d'analyse de complexité (au pire et en moyenne) des algorithmes de l'élection.
Document type :
Reports
Complete list of metadata

https://hal.inria.fr/inria-00074554
Contributor : Rapport de Recherche Inria <>
Submitted on : Wednesday, May 24, 2006 - 3:45:05 PM
Last modification on : Thursday, February 11, 2021 - 2:48:05 PM
Long-term archiving on: : Tuesday, April 12, 2011 - 5:29:44 PM

Identifiers

  • HAL Id : inria-00074554, version 1

Citation

Christian Lavault. Complexité de l'élection. [Rapport de recherche] RR-2118, INRIA. 1993. ⟨inria-00074554⟩

Share

Metrics

Record views

182

Files downloads

136