Élection autostabilisante en un nombre polynomial de pas de calcul

International audienceCet article est un résumé étendu de [1] dans lequel nous présentons un algorithme distribué autostabilisant et silencieux d'élection de leader. Cet algorithme est écrit dans le modèle à états et prouvé sous l'hypothèse d'un démon distribué inéquitable, le démon le plus général du modèle. Il stabilise en Θ(n) rondes, Θ(n^3) pas et nécessite Θ(log n) bits par processus, où n est le nombre de processus. C'est à notre connaissance le premier algorithme autostabilisant asynchrone d'élection pour lequel une borne supérieure sur le temps de stabilisation en nombre de pas de calcul est prouvée