Description
Date depot: 8 avril 2019
Titre: Algorithmes de diffusion ordonnée dans les systèmes répartis dynamiques
Encadrante :
Luciana ARANTES (LIP6)
Directeur de thèse:
Pierre SENS (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Assurer un ordre de réception des messages dans les protocoles de dissémination d’informations est un élément essentiel dans les systèmes répartis . Par exemple, garantir un ordre total dans les traitements permet d’implémenter une machine à état répliquée. Une diffusion causale est, quant à elle, à la base de nombreux mécanismes pour disséminer une information cohérente dans les réseaux sociaux ou pour réaliser des systèmes de publications/abonnements.
Il s’agit alors de propager une information à un ensemble de nœuds tout en respectant des contraintes d’ordre et/ou de causalité entre les informations.
Les diffusions causales et totalement ordonnées ont été largement étudiées dans des systèmes répartis statiques . Cependant, la dynamicité est une propriété clé des nouvelles infrastructures distribuées : par exemple, dans l’internet des objets, les nœuds physiques peuvent arriver et partir à tout moment, être sujet à des fautes ou encore se déplacer.
Cette thèse vise à étudier les protocoles de diffusion ordonnée dans le cadre de ces systèmes où la topologie est fortement dynamique et les ressources des nœuds limitées. Dans le cadre de la diffusion causale, la plupart des algorithmes existant repose sur des vecteurs d’horloges de Mattern de taille N (N étant les nombre de processus du système) pour capturer les informations de causalité. Ces vecteurs, éventuellement compressés, sont transportés dans les messages. De telles implémentations sont coûteuses, ne passent pas à l’échelle et ne permettent pas de gérer la dynamicité. D’autres implémentations réduisent les informations transmises mais reposent sur l’hypothèse forte de canaux de communications FIFO .
Pour la diffusion totalement ordonnée, les approches déterministes passent mal à l’échelle. Récemment, des approches probabilistes abordent le passage à l’échelle et gèrent l’arrivée et le départ de nœuds notamment dans le contexte des réseaux pair-à-pair.
L’objectif de cette thèse est de proposer et implémenter de nouveaux algorithmes de diffusion ordonnée prenant en compte les caractéristiques d’un réseau dynamique telles que l’évolution dans le temps de la topologie du graphe d’interconnexion, les fautes, la consommation énergétique, la charge des nœuds, ou encore des contraintes mémoires.
Ces algorithmes sont être ensuite déployés sur un ensemble de nœuds physiques et testés dans un environnement de simulation tel qu’OMNet++.
Doctorant.e: Wilhelm Daniel