BERNARD Samuel

doctorant à Sorbonne Université
Équipe : NPA
https://lip6.fr/Samuel.Bernard

Direction de recherche : Sébastien TIXEUIL

Co-encadrement : POTOP-BUTUCARU Maria

Algorithmique répartie : vaincre les contraintes des réseaux modernes

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 multijoueur. 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.

Soutenance : 10/12/2010

Membres du jury :

Eddy Caron, MCF. HDR, ENS de Lyon [Rapporteur]
Bertrand Ducourthial, Professeur, UTC [Rapporteur]
Serge Fdida, Professeur, UPMC
Fabien Mathieu, Ing. de rech., Orange Labs
Gwendal Simon, MCF., Telecom Bretagne
Sébastien Tixeuil, Professeur, UPMC
Maria Potop-butucaru, MCF., UPMC

Date de départ : 10/12/2010

Publications 2008-2012