PhD Thesis of Arnaud Favier
On Wednesday 2 March 2022, I defended my PhD in Computer Science, more precisely in distributed systems, entitled “Eventual Leader Elections in Dynamic Networks” at Sorbonne University in Paris.
This PhD thesis was advised by Pierre Sens and co-advised by Luciana Arantes, with the help of Jonathan Lejeune.
This research work was funded by a CORDI-S grant from Inria Paris.
Jury members
The jury of the PhD defense was composed of 7 members:
- Emmanuelle Anceaume (CNRS) - Reviewer
- Denis Conan (Télécom SudParis) - Reviewer
- Anne Fladenmuller (Sorbonne University) - Examiner
- Mikel Larrea (University of the Basque Country) - Examiner
- Luciana Arantes (Sorbonne University) - Advisor
- Pierre Sens (Sorbonne University) - Supervisor
- Jonathan Lejeune (Sorbonne University) - Invited
Abstract in English 🇬🇧
Leader election is important for many fault-tolerant services in asynchronous distributed systems. By coordinating actions of a set of distributed 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.
Abstract in French 🇫🇷
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é.
Thesis manuscript
Download the thesis manuscript with the following link or find it on TEL/HAL thèses (archives-ouvertes.fr):
–> Thesis Arnaud Favier - Eventual Leader Elections in Dynamic Networks.pdf
