Soutenance Thèse Léon Lim

29 novembre 2012

Léon Lim soutiendra sa thèse de doctorat jeudi 29 Novembre 2012.

Sujet : Gestion de groupe partitionnable dans les réseaux mobiles spontanés

La soutenance aura lieu jeudi 29 Novembre à 14h dans la salle C06, à Télécom SudParis, 9 rue Charles Fourier, 91000 Evry devant un jury composé de :

Pascal Felber, Professeur à l'Université de Neuchâtel, Rapporteur
Achour Mostefaoui, Professeur à l'Université de Nantes, Rapporteur
Pierre Sens, Professeur à l'Université Pierre et Marie Curie, Examinateur
André Schiper, Professeur à l'École Polytechnique Fédérale de Lausanne, Examinateur
Guy Bernard, Professeur à Télécom SudParis, Directeur de thèse
Denis Conan, Maître de Conférences à Télécom SudParis, Encadrant

Résumé :

Dans les réseaux mobiles spontanés (en anglais, Mobile Ad hoc NETworks ou MANETs), la gestion de groupe partitionnable est un service de base permettant la construction d'applications réparties tolérantes au partitionnement, c'est-à-dire dans lesquelles plusieurs groupes de processus évoluent concurremment et indépendamment les uns des autres. En deux décennies, plusieurs spécifications de ce service ont été proposées. Toutefois, aucune de ces spécifications ne satisfait les deux exigences antagonistes suivantes : 1) elle doit être assez forte pour fournir des garanties utiles aux applications réparties dans les systèmes partitionnables; 2) elle doit être assez faible pour être résoluble (implantable). Dans cette thèse, nous proposons une spécification et une implantation de la gestion de groupe partitionnable en environnement réseaux très dynamiques tels que les MANETs.

Après une étude approfondie des problèmes dans les spécifications de la littérature et une identification des caractéristiques des MANETs, nous proposons un modèle de système qui caractérise la stabilité  dans les MANETs.
Les nœuds mobiles (processus) qui restent dans une partition pendant une période de temps assez longue sont dits stables. Un critère de stabilité basé sur le
comptage des battements de cœur est proposé afin de sélectionner les nœuds les plus stables, c'est-à-dire les nœuds faisant partie d'une éventuelle partition stable. Puisque les processus stables et instables peuvent coexister dans une partition, nous définissons une condition de stabilité de α processus stables dans une partition pour assurer la progression et la terminaison des exécutions, et ceci même si la partition n'est pas complètement stable.

Ensuite, nous adaptons pour les systèmes partitionnables l'approche Paxos à base de consensus Synod. Cette adaptation résulte en la spécification d'un consensus
abandonnable AC construit au-dessus d'un détecteur ultime des α participants d'une partition ♢PPD et d'un registre ultime par partition ♢RPP. ♢PPD garantit la vivacité dans une partition même si la partition n'est pas complètement stable tandis que ♢RPP préserve la sûreté dans la même partition. Le rôle de ♢PPD est de capturer le compromis entre l'accord et la progression en détectant ultimement la condition de stabilité et en fournissant un leader parmi ces processus. ♢RPP fournit la mémoire répartie (ou registre) partagée dans la même partition.

Enfin, la gestion de groupe partitionnable est résolue en la transformant en une séquence d'instances de AC, où chaque instance de AC est exécutée par les
processus participants dans la vue successeur potentielle. Quand la décision est retournée par l'instance de AC est un ensemble de processus α-Set muni d'un
identifiant, ces processus et l'identifiant constituent la vue successeur. La décision peut être la valeur spécifique (⊥,⊥) signifiant que l'instance de AC a été abandonnée car la condition de stabilité  n'est pas satisfaite. Chacun des modules ♢PPD, ♢RPP, AC et gestion de groupe partitionnable est implanté et prouvé. Par ailleurs, nous analysons les performances de ♢PPD par simulation.

Mots clefs : MANETs, systèmes partitionnables, gestion de groupe partitionnable, consensus abandonnable

Événements