Direction de recherche : Pierre SENS

Co-encadrement : ARANTES Luciana

Algorithmes de diffusion causale dans les systèmes répartis dynamique

La diffusion causale est un élément fondamental de nombreuses applications distribuées ou parallèles, telles que les bases de données distribuées, les publications-abonnements, ou les réseaux sociaux, qui ont tous besoin de partager des informations entre tous les participants (par exemple, les processus, machines, etc.), en respectant la causalité entre les messages échangés. Les algorithmes de diffusion causale existants ne passent soit pas à l'échelle, soit ils ne tolèrent pas toujours les dynamiques introduites par les processus qui rejoignent ou quittent le système, qui échouent pendant l'exécution, ou qui modifient leur ensemble de canaux de communication. Certains travaux ajoutent aux messages toutes les informations nécessaires pour les ordonner causalement à la réception. Cependant, il a été prouvé qu'une structure avec une entrée par processus du système est la structure minimale requise pour caractériser la causalité. Par conséquent, les algorithmes qui utilisent une telle structure pour caractériser la causalité ne passent pas à l'échelle.
D'autres travaux passent à l'échelle en faisant des hypothèses sur le système, comme la topologie du réseau ou la propriété FIFO des canaux de communication. En revanche, ils ne couvrent pas toutes les dynamiques possibles des systèmes distribués.
Dans cette thèse, nous proposons des algorithmes de diffusion causale qui passent à l'échelle et tolèrent les dynamiques des systèmes distribués. Nous proposons d'abord un algorithme de diffusion causale pour les réseaux mobiles, composés de nœuds mobiles connectés par un réseau sans fil et de stations de support connectées par des canaux filaires. Ces réseaux ont des caractéristiques spécifiques : des capacités limitées des nœuds mobiles (calcul, stockage, énergie), des canaux de communication peu fiables, et des dynamiques de connexions dues à la mobilité des nœuds, à l'échec, et aux opérations d'entrée/sortie. Nous avons implémenté notre algorithme dans OMNeT++/INET. Dans la seconde partie, nous proposons un détecteur d'erreurs pour les algorithmes implémentant la diffusion causale avec les horloges à M entrées, ainsi qu'une nouvelle horloge logique construite avec des horloges probabilistes.
Nous avons implémenté les algorithmes dans OMNeT++.

Publications 2020-2023

• 2023
  • D. Wilhelm : “Causal broadcast algorithms for dynamic distributed systems”, thèse, soutenance 17/05/2023, direction de recherche Sens, Pierre, co-encadrement : Arantes, Luciana (2023)
  • D. Wilhelm, L. Arantes, P. Sens : “DCS : A logical clock composed of a dynamic set of probabilistic clocks”, AlgoTel 2023 - 25^es Rencontres Francophones sur les Aspects Algorithmiques des Télécommunications, Cargèse, France (2023)
  • D. Wilhelm, L. Arantes, P. Sens : “A probabilistic Dynamic Clock Set to capture message causality”, (2023)
• 2022
  • D. Wilhelm, L. Arantes, P. Sens : “A scalable causal broadcast that tolerates dynamics of mobile networks”, 23^rd International Conference on Distributed Computing and Networking (ICDCN), New Delhi / Virtual, India (2022)
• 2020
  • D. Wilhelm, L. Arantes, P. Sens : “A scalable causal broadcast that tolerates dynamics of mobile networks”, (2020)