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.
Type de document :
Rapport
[Rapport de recherche] RR-2118, INRIA. 1993
Liste complète des métadonnées

https://hal.inria.fr/inria-00074554
Contributeur : Rapport de Recherche Inria <>
Soumis le : mercredi 24 mai 2006 - 15:45:05
Dernière modification le : mercredi 16 mai 2018 - 11:23:03
Document(s) archivé(s) le : mardi 12 avril 2011 - 17:29:44

Fichiers

Identifiants

  • HAL Id : inria-00074554, version 1

Citation

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

Partager

Métriques

Consultations de la notice

150

Téléchargements de fichiers

73