Direction de recherche : Pierre SENS

Co-encadrement : ARANTES Luciana

Elections de leader ultime dans les réseaux dynamiques

L'élection de leader est importante pour les services tolérants aux pannes dans les systèmes distribués asynchrones. En coordonnant les actions d'un ensemble de processus, 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é 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.
Plusieurs 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, des chemins plus courts vers le leader, et une meilleure stabilité.

Publications 2019-2022

• 2022
  • A. Favier : “Elections de leader ultime dans les réseaux dynamiques”, soutenance de thèse, soutenance 02/03/2022, direction de recherche Sens, Pierre, co-encadrement : Arantes, Luciana (2022)
• 2021
  • A. Favier, L. Arantes, J. Lejeune, P. Sens : “Centrality-Based Eventual Leader Election in Dynamic Networks”, NCA 2021 - 20^th IEEE International Symposium on Network Computing and Applications, 2021 IEEE 20^th International Symposium on Network Computing and Applications (NCA), Cambridge, Boston, United States, pp. 1-8 (2021)
• 2020
  • A. Favier, N. Guittonneau, L. Arantes, A. Fladenmuller, J. Lejeune, P. Sens : “Topology Aware Leader Election Algorithm for Dynamic Networks”, PRDC 2020 - 25^th IEEE Pacific Rim International Symposium on Dependable Computing, 2020 IEEE 25^th 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)
• 2019
  • 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)