Supervision : Pierre SENS
Co-supervision : ARANTES Luciana
Eventual Leader Elections in Dynamic Networks
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.
Defence : 03/02/2022
Jury members :
ANCEAUME Emmanuelle (Research Director, CNRS) [Rapporteur]
CONAN Denis (Associate Professor HDR, Télécom SudParis) [Rapporteur]
FLADENMULLER Anne (Professor, Sorbonne University)
LARREA Mikel (Professor, University of the Basque Country)
ARANTES Luciana (Associate Professor, Sorbonne University)
SENS Pierre (Professor, Sorbonne University)
LEJEUNE Jonathan (Associate Professor, Sorbonne University)
- A. Favier : “Elections de leader ultime dans les réseaux dynamiques”, thesis, defence 03/02/2022, supervision Sens, Pierre, co-supervision : Arantes, Luciana (2022)
- A. Favier, L. Arantes, J. Lejeune, P. Sens : “Centrality-Based Eventual Leader Election in Dynamic Networks”, NCA 2021 - 20th IEEE International Symposium on Network Computing and Applications, 2021 IEEE 20th International Symposium on Network Computing and Applications (NCA), Cambridge, Boston, United States, pp. 1-8 (2021)
- A. Favier, N. Guittonneau, L. Arantes, A. Fladenmuller, J. Lejeune, P. Sens : “Topology Aware Leader Election Algorithm for Dynamic Networks”, PRDC 2020 - 25th IEEE Pacific Rim International Symposium on Dependable Computing, 2020 IEEE 25th Pacific Rim International Symposium on Dependable Computing (PRDC), Perth, Australia, pp. 1-10 (2020)
- A. Favier, N. Guittonneau, J. Lejeune, A. Fladenmuller, L. Arantes, P. Sens : “Topology Aware Leader Election Algorithm for MANET”, COMPAS 2020 - Conférence francophone d'informatique en Parallélisme, Architecture et Système, Lyon, France (2020)
- A. Favier, N. Guittonneau, L. Arantes, A. Fladenmuller, P. Sens : “Un algorithme d’élection de leader cross-layer pour réseaux mobiles ad hoc (résumé)”, COMPAS 2019 - Conférence d'informatique en Parallélisme, Architecture et Système, Anglet, France (2019)