Eventual Leader Elections in Dynamic Networks
Elections de leader ultime dans les réseaux dynamiques
Résumé
Leader election is important for many fault-tolerant services in asynchronous distributed systems. By coordinating actions of a set of processes, it allows solving agreement problems like the consensus, a fundamental problem of distributed computing. Several consensus algorithms, such as Paxos, rely on an eventual leader election service, also known as the Omega failure detector. Omega returns the identity of a process in the system, ensuring that eventually the identity of the same correct process is always returned. Many leadership algorithms were proposed in the literature to implement Omega. Among those that consider dynamic systems, most of them do not choose the leader according to a topological criterion. However, the position of the leader in the network directly impacts the performance of algorithms using the leader election service, since the leader must often interact with other processes, for example, to collect information from a majority of processes in consensus algorithms. This thesis studies the eventual leader election problem in dynamic evolving networks and performance related issues. Two eventual leader election algorithms are proposed for Mobile Ad Hoc Networks. They maintain and exploit the knowledge of the network topology to eventually elect one leader per connected component with the best closeness centrality. Evaluations were conducted on simulators with different mobility models and performance results show that these algorithms present better performance than other algorithms of the literature, including fewer messages, shortest paths to the leader, and better stability.
L'élection de leader est importante pour les services tolérants aux pannes dans les systèmes distribués asynchrones. En coordonnant les actions d'un ensemble de processus, 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é 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. Plusieurs 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, des chemins plus courts vers le leader, et une meilleure stabilité.
Origine : Version validée par le jury (STAR)