PhD graduated
Team : DELYS
Departure date : 04/30/2022

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)

Departure date : 04/30/2022

2019-2022 Publications