L’élection de leader est importante pour les services tolérants aux pannes dans les systèmes distribués (également appelés systèmes répartis) asynchrones. En coordonnant les actions d’un ensemble de processus distribués, elle permet de résoudre des problèmes d’accord comme le consensus, un problème fondamental en informatique distribuée. Des algorithmes de consensus, tel que Paxos, s’appuient sur un service d’élection de leader ultime, également appelé détecteur de défaillances Omega (Ω). Omega renvoie l’identité d’un processus du système et garantit qu’après un certain temps, l’identité du même processus correct est toujours renvoyée.
De nombreux algorithmes d’élection de leader ont été proposés dans la littérature pour implémenter Omega. Parmi ceux considérant les systèmes dynamiques, la plupart ne choisissent pas le leader selon un critère topologique. Or, la position du leader dans le réseau impacte directement les performances des algorithmes utilisant le service d’élection, car le leader doit souvent interagir avec les autres processus pour, par exemple, collecter les informations d’une majorité de processus dans le cas du consensus.
Cette thèse étudie le problème d’élection de leader ultime dans les réseaux dynamiques. Deux algorithmes d’élection sont proposés pour les réseaux mobiles ad hoc. Ceux-ci maintiennent et exploitent la connaissance de la topologie du réseau pour élire à terme un unique leader par composante connexe ayant la meilleure centralité de proximité. Des évaluations sur simulateurs avec différents modèles de mobilité montrent que ces algorithmes présentent de meilleures performances que d’autres algorithmes de la littérature, notamment moins de messages échangés, des chemins plus courts vers le leader, et une meilleure stabilité.