PIC PIC PIC PIC PIC

Thesis submitted for the degree of

Doctor of Philosophy in Computer Science

Eventual Leader Elections in Dynamic Networks

Arnaud FAVIER

2 March 2022

Sorbonne Université

Institut National de Recherche en Sciences et Technologies du Numérique

Laboratoire d’Informatique de Sorbonne Université

Centre national de la recherche scientifique

École Doctorale Informatique, Télécommunications et Électronique (Paris)

Jury members

Reviewers Emmanuelle ANCEAUME Research Director, CNRS
  Denis CONAN Associate Professor HDR, Télécom SudParis
Examiners Anne FLADENMULLER Professor, Sorbonne University
  Mikel LARREA Professor, University of the Basque Country
Advisor Pierre SENS Professor, Sorbonne University
Co-advisor Luciana ARANTES Associate Professor, Sorbonne University
Invited Jonathan LEJEUNE Associate Professor, Sorbonne University

_______________________________________________________________________________________

Abstract
Résumé (Abstract in French)
Acknowledgments
Contents
List of Figures
List of Tables
1 Introduction
1.1 Contributions
1.2 Manuscript Organization
1.3 Publications
2 Background
2.1 Properties of Distributed Algorithms
2.2 Timing Models
2.3 Process Failures
2.4 Communication Channels
2.5 Failures of Communication Channels
2.6 Distributed Systems
2.7 Centralities
2.8 Messages Dissemination
2.9 Leader Election
2.10 Conclusion
3 Related Work
3.1 Classical Leader Election Algorithms
3.2 Eventual Leader Election Algorithms
3.3 Conclusion
4 Topology Aware Leader Election Algorithm for Dynamic Networks
4.1 System Model and Assumptions
4.2 Topology Aware Leader Election Algorithm
4.3 Simulation Environment
4.4 Evaluation
4.5 Conclusion
5 Centrality-Based Eventual Leader Election in Dynamic Networks
5.1 System Model and Assumptions
5.2 Centrality-Based Eventual Leader Election Algorithm
5.3 Simulation Environment
5.4 Evaluation
5.5 Conclusion
6 Conclusion and Future Work
6.1 Contributions
6.2 Future Directions
A Appendix
A.1 Energy consumption per node
Bibliography