Complexité de l'élection: méthodes d'analyse d'algorithmes distribués
Lavault, Christian
HAL, hal-00464405 / Harvested from HAL
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 où 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 complexité en communication des algorithmes, i.e. anneaux synchrones ou asynchrones mais aussi anneaux avec ou sans information structurelle («sens de la direction», connaissance exacte ou approchée de la taille de l'anneau, etc.) ― tous types de connaissance à même d'améliorerconsidérablement la complexité 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. Elle constitue également une tentative pour faire le point sur les diverses méthodes d'analyse de complexité des algorithmes d'élection, en particulier les méthodes probabilistes
Publié le : 1995-07-05
Classification:  Analyse algorithme,  Complexité algorithme,  Processus communication,  Méthode analyse,  Anneau,  Asynchrone,  Synchrone,  Algorithmique,  [MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO],  [INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
@article{hal-00464405,
     author = {Lavault, Christian},
     title = {Complexit\'e de l'\'election: m\'ethodes d'analyse d'algorithmes distribu\'es},
     journal = {HAL},
     volume = {1995},
     number = {0},
     year = {1995},
     language = {fr},
     url = {http://dml.mathdoc.fr/item/hal-00464405}
}
Lavault, Christian. Complexité de l'élection: méthodes d'analyse d'algorithmes distribués. HAL, Tome 1995 (1995) no. 0, . http://gdmltest.u-ga.fr/item/hal-00464405/