Description
Date depot: 1 janvier 1900
Titre: Algorithmique répartie : vaincre les contraintes des réseaux modernes
Directeur de thèse:
Sébastien TIXEUIL (LIP6)
Directrice de thèse:
Maria POTOP-BUTUCARU (LIP6)
Domaine scientifique: Sciences et technologies de l'information et de la communication
Thématique CNRS : Non defini
Resumé:
Dans cette thèse, nous examinons trois types de réseaux très différents. Les réseaux {unidirectionnels anonymes}, pouvant servir de modèle à des réseaux de capteurs légers communicant sans fil. Les réseaux dits « {pair-à-pair} » permettant l'interaction de milliers voire de millions d'utilisateurs différents. Et enfin les réseaux {distribués} « classiques » servant de base à des jeux vidéo répartis utilisant des dizaines de nœuds. Le point commun de nos travaux est que nous prenons en compte, à chaque fois, un type de panne (ou faute) caractéristique du réseau sous-jacent.
Ainsi, dans les réseaux unidirectionnels, nous résolvons le problème de {coloriage de sommets} de manière {auto-stabilisante}. Ce problème, qui est à la base de nombreux algorithmes distribués, fournit une indication claire de la différence de complexité algorithmique avec les réseaux bidirectionnels. Le caractère auto-stabilisant nous assure que, même après un nombre arbitraire de fautes, l'algorithme retrouvera un fonctionnement correct, sans intervention extérieure.
Dans les réseaux pair-à-pair, nous nous attaquons à deux des principales difficultés de ce type de réseau : l'{attrition} et la {sécurité}. Nous étudions ainsi la faisabilité d'un système de {sauvegarde collaborative} par rapport à un taux élevé d'attrition, c'est-à-dire face à un grand nombre de départs et d'arrivées pendant l'exécution du système. Ensuite, nous présentons un {algorithme de test de secrets à divulgation nulle} de connaissance, utilisé par les pairs pour savoir s'ils partagent un même secret. Les pannes sont alors représentées par la présence d'utilisateurs malicieux cherchant à corrompre le système.
Enfin, au travers de la thématique des jeux vidéo, nous proposons un algorithme {optimiste} et {robuste} de {diffusion totalement ordonnée} pour résoudre le problème de {cohérence}. Ce problème se pose lorsque que l'on distribue la simulation d'un système, ici un jeu vidéo multi-joueurs. Nous assurons le maintien de cette cohérence même en présence de fautes, matérialisées ici par un crash ou la déconnexion de certains joueurs.
Doctorant.e: Bernard Samuel