Description
Date depot: 1 janvier 1900
Titre: Accords distribués dans les réseaux dynamiques
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é:
{{{Contexte et positionnement scientifique}}}
Le contexte général est la définition de nouveaux services dans les réseaux de nouvelle génération. Dans ces réseaux des stations de base peuvent diffuser et partager des informations multi-média à l’ensemble des périphériques mobiles présents à portée. Avec z’augmentation de la densification, les stations ne pourront plus à elles seules assurer la propagation des informations. Les nouveaux services doivent donc exploiter les possibilités de communication directe entre les périphériques mobiles. Il faut donc repenser les protocoles de base pour les adapter aux contraintes de mobilité des périphériques associés aux utilisateurs.
La {{dynamicité}} est donc une propriété clé des nouvelles infrastructures réparties : les périphériques physiques dans le cadre des nouveaux réseaux ou les machines virtuelles dans le cadre de clouds peuvent arriver et partir à tout moment, être sujet à des fautes ou encore se déplacer. Cela pose des nouveaux défis pour les algorithmes répartis qui usuellement considèrent des topologies connues et statiques.
Cette thèse vise donc à étudier des {{algorithmes d’accord}} qui sont au cœur des applications répartis s’exécutant sur les {{réseaux dynamiques}}. On retrouve ces algorithmes dans la plupart des services permettant de répliquer et partager des données entre utilisateurs. Le plus fondamental des problèmes d’accord est celui du consensus [2,3]: il s’agit à terme que tous les utilisateurs du système décident une et une seule valeur parmi un ensemble de valeurs proposées. Le consensus permet de répliquer de manière cohérente de données. Il est ainsi massivement utilisé dans les systèmes de bases de données répartis. Le plus célèbre des algorithmes de consensus est Paxos [6] proposé par Leslie Lamport (prix Turing 2014) et utilisé par
Google pour maintenir la cohérence dans ses index répliqués.
Le consensus a été largement étudié dans des configurations à petite et grande échelle en considérant par exemple des délais de transmission entre les nœuds pouvant être très longs mais bornés. En revanche, très peu de travaux se sont concentrés sur les cas où la topologie évolue dynamiquement et sur les hypothèses de stabilité nécessaires dans le réseau pour assurer la convergence de l’algorithme
[7].
{{{Objectif de la thèse}}}
L’objectif de la thèse est double :
D’un point de vue algorithmique : il s’agit de {{définir des algorithmes de consensus adaptés aux topologies dynamiques}}. Ces algorithmes s’appuieront sur un modèle de graphe dynamique inspiré des TVG (Time Varying Graph) [8]. Outre l’aspect purement algorithmique il s’agit, d’un point de vue théorique, d’identifier les conditions nécessaires et suffisantes dans le graphe pour assurer la correction de l’algorithme tant en termes de sûreté (deux valeurs différentes ne peuvent être décidées) qu’en termes de vivacité (tous les participants corrects doivent décider d’une valeur). Les rares travaux existant sur l’algorithmique en présence de mobilité et de fautes font des hypothèses fortes et non réalistes sur legraphe sous-jacent en considérant souvent à terme soit un graphe statique soit un graphe sans partition [9,10]. Or dans la réalité le graphe reliant les nœuds est en perpétuelle évolution. La question fondamentale est : « peut-on assurer un consensus déterministe dans un graphe dynamique et sous quelle condition minimale de stabilité sur la topologie ? ».
D’un point de vue expérimental, une des originalités de cette thèse est d’allier aux aspects théoriques des validations expérimentales. Les algorithmes proposés seront implémentés au-dessus de d’environnements comme OMnet++ qui permettent de simuler finement des environnements distribués en présence de nœuds mobiles. Les algorithmes seront testés avec différents modèles de mobilité reconnus par la communauté comme le modèle Smooth. Nous viserons également à rejouer des traces de mobilité issues d’expériences réelles menées au sein du Labex. Notamment, il serait intéressant d’interagir avec le Lutin pour obtenir des traces d’interactions et de mobilité des visiteurs de la cité des Sciences.
{{{Références}}}
[1] Chandra, T., Toueg, S.: Unreliable failure detectors for reliable distributed systems. JACM 43(2) (March 1996) 225–267
[2] Dwork, C., Lynch, N.A., Stockmeyer, L.: Consensus in the presence of partial synchrony. J.ACM 35(2), 288–323 (1988)
[3] Fischer, M.J., Lynch, N.A., Paterson, M.S.: Impossibility of distributed consensus with one faulty process. J. ACM 32(2), 374–382 (1985)
[4] Udo Fritzke Jr., Philippe Ingels, Achour Mostefaoui, and Michel Raynal. Consensus-Based Fault-Tolerant Total Order Multicast. IEEE Transactions On Parallel and Distributed Systems, Vol. 12, NO. 2, Feb 2001
[5] Tushar D. Chandra, Robert Griesemer, and Joshua Redstone. 2007. Paxos made live: an engineering perspective. In Proceedings of the twenty-sixth annual ACM symposium on Principles of distributed computing (PO
Doctorant.e: Jeanneau Denis