Complexité de l'élection

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