Acknowledgments

First, I am particularly thankful to my advisors Pierre Sens and Luciana Arantes, for their guidance, advice, and support throughout these years. Thank you Pierre for accepting me as your student, and for always answering my many questions. I learned a lot from you and it was always a real pleasure to work with you. Thank you Luciana for your kindness and your many precise proofreading. I really enjoyed working with you, as well as our discussions on grammar points among many other subjects. Thank you to both of you for teaching me how to do research and much more.

I am also thankful to Jonathan Lejeune, for his help and advice during this thesis. Thank you Jonathan for the opportunity to teach with you in Master, which led to the work of the first contribution with PeerSim.

Then, I would like to thank Emmanuelle Anceaume and Denis Conan for accepting to review this thesis, and for the time and efforts dedicated to evaluating it. I also want to thank Anne Fladenmuller and Mikel Larrea for accepting to be part of this jury as examiners.

I am grateful to Inria for the CORDI-S grant and to Sorbonne Université for the working and academic environment. I would like to thank my colleagues at LIP6 and especially the permanents and other Ph.D. students of the Delys team, for our interesting discussions and the good time during the Winter Schools and the Compas conference. A special thanks to Saalik, Daniel, and Mathieu for your support. I also want to thank Anne and Nicolas for their collaboration.

I would like to thank Kamel and the team from the reproduction workshop of Sorbonne Université for their kindness and their careful work.

This thesis is a milestone in my computer science journey, which started with a passion at the age of eight, and has been enriched by several people over the years.

I would like to thank Sara Bouchenak for her guidance and recommendation to meet Pierre when I was a software engineer student at INSA Lyon. I also want to thank Sonia Ben Mokhtar and Guillaume Salagnac for their advice to explore the world of scientific research.

I am thankful to all my teachers at the IUT of Bourg-en-Bresse, for their solid teaching of computer science fundamentals, for showing the possibilities of studying this field further, and for giving me the opportunity to do so.

I am also grateful to my high school teacher Jean-Baptiste Butet, my mentor in London Bertrand, my colleague in Dublin Aleksandar, my uncles Jean-Luc and Pierre, my classmate Tom, as well as my neighbor Roland, who all directly contributed to this journey.

Arriving in Paris to start a Ph.D. was a challenge, but many people made it easier.

I am thankful to thank Stéphanie for her support, trust, and career advice during these years.

I would like to thank Friedrich for his support and advice throughout our discussions during and after the lockdown.

I want to thank all my friends from INSEAD for their constant support, discussions and moments spent together. In particular, thanks to Maéva, Dalia, Marianna, Maurits and Clément.

I also would like to thank my friends from INSA: Anthony, Paul-Louis, Mathis, and Sylvain for their support and our good times in Paris.

I want to thank my friends from the IUT and Lyon: Aurélien, Corentin, Valentin, Quentin, and Florian for their support and listening, with a special thanks to Bastien for his entire trust, help, and dedication to our projects, without whom many things would not have been possible.

I also would like to thank Rémi, Olivier, Louis, Audrey, and Jean for their support and game nights.

I am thankful to Jonathan, Elsa, Leslie, Catherine, and Jean-Marc for their help and support in Paris.

I am also grateful to Louise, Monique, and Christian for their support during their visits to Paris, where I was always included with them.

I would like to thank my close friend Matthieu for his support and constant optimism during these years, with all our good times with Aurélie for many years, especially in the Morvan.

I want to thank Marie very much for her support and understanding during these years, as well as for the time off in Angers. Thank you for being by my side, you continue to impress me every day.

I also would like to thank all my family for their support and understanding during these years.

I am thankful to my sister Laëtitia and my brother-in-law Benoit for their support and precious help at the beginning in Paris, as well as for our good times in Mallorca. I also would like to thank my brother Cédric and my sister-in-law Marie-Line for their support and their visits to Paris.

I am truly grateful to my grandmother Marcelle “Mamy Coucou” for her happiness and enthusiasm giving me motivation and energy every day.

Last but not least, I am deeply grateful to my parents, Jean-Claude Favier and Marie Favier, for their flawless support and trust for many years, including these in Paris. Thank you for teaching me to be curious and to work, as well as giving me lucid advice and encouraging me in all situations.
Merci infiniment pour tout ce que vous faites.
Like what, bringing a computer at home, and then doing the IUT open days, was quite an idea!

I am also thankful to all the people not explicitly mentioned above, who helped me during these years.


Table of Contents

1 Introduction
1.1 Contributions
1.1.1 Topology Aware Leader Election Algorithm for Dynamic Networks
1.1.2 Centrality-Based Eventual Leader Election in Dynamic Networks
1.2 Manuscript Organization
1.3 Publications
1.3.1 Articles in International Conferences
1.3.2 Articles in National Conferences
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.6.1 Static Systems
2.6.2 Dynamic Systems
2.7 Centralities
2.8 Messages Dissemination
2.9 Leader Election
2.9.1 Classical Leader Election
2.9.2 Eventual Leader Election
2.10 Conclusion
3 Related Work
3.1 Classical Leader Election Algorithms
3.1.1 Static Systems
3.1.2 Dynamic Systems
3.2 Eventual Leader Election Algorithms
3.2.1 Static Systems
3.2.2 Dynamic Systems
3.3 Conclusion
4 Topology Aware Leader Election Algorithm for Dynamic Networks
4.1 System Model and Assumptions
4.1.1 Node states and failures
4.1.2 Communication graph
4.1.3 Channels
4.1.4 Membership and nodes identity
4.2 Topology Aware Leader Election Algorithm
4.2.1 Pseudo-code
4.2.2 Data structures, variables, and messages (lines 1 to 6)
4.2.3 Initialization (lines 7 to 11)
4.2.4 Periodic updates task (lines 12 to 16)
4.2.5 Connection (lines 20 to 23)
4.2.6 Disconnection (lines 24 to 27)
4.2.7 Knowledge reception (lines 28 to 38)
4.2.8 Updates reception (lines 39 to 53)
4.2.9 Pending updates (lines 54 to 65)
4.2.10 Leader election (lines 17 to 19)
4.2.11 Execution examples
4.3 Simulation Environment
4.3.1 Algorithms
4.3.2 Algorithms Settings
4.3.3 Mobility Models
4.4 Evaluation
4.4.1 Metrics
4.4.2 Instability
4.4.3 Number of messages sent per second
4.4.4 Path to the leader
4.4.5 Fault injection
4.5 Conclusion
5 Centrality-Based Eventual Leader Election in Dynamic Networks
5.1 System Model and Assumptions
5.1.1 Node states and failures
5.1.2 Communication graph
5.1.3 Channels
5.1.4 Membership and nodes identity
5.2 Centrality-Based Eventual Leader Election Algorithm
5.2.1 Pseudo-code
5.2.2 Data structures, messages, and variables (lines 1 to 4)
5.2.3 Initialization (lines 5 to 7)
5.2.4 Node connection (lines 8 to 17)
5.2.5 Node disconnection (lines 18 to 23)
5.2.6 Knowledge update (lines 24 to 34)
5.2.7 Neighbors update (lines 35 to 41)
5.2.8 Information propagation (lines 42 to 47)
5.2.9 Leader election (lines 48 to 52)
5.3 Simulation Environment
5.3.1 Algorithms Settings
5.3.2 Mobility Models
5.4 Evaluation
5.4.1 Metrics
5.4.2 Average number of messages sent per second per node
5.4.3 Average of the median path to the leader
5.4.4 Instability
5.4.5 Focusing on the 60 meters range over time
5.4.6 A comparative analysis with Topology Aware
5.5 Conclusion
6 Conclusion and Future Work
6.1 Contributions
6.2 Future Directions
A Appendix
A.1 Energy consumption per node
A.1.1 Simulation environment
A.1.2 Algorithms settings
A.1.3 Mobility Models
A.1.4 Metric
A.1.5 Performance Results