Master 2013 2014
Stages de la spécialité SAR
Mariage maximal auto-stabilisant et systèmes répartis dynamiques


Lieu :LIP6, Campus Jussieu, 4 place Jussieu, 75005 Paris, France
Encadrant : Swan Dubois et Franck Petit Equipe-projet Inria REGAL <Prenom>.<Nom>@lip6.fr
Dates :04/2014 au 09/2014
Rémunération :Oui
Mots-clés : Parcours SAR autre qu’ATIAM, recherche

Description

Contexte

Ce stage propose de s’intéresser au problème du mariage maximal dans les systèmes répartis. Si on représente le réseau de communication par un graphe non-orienté, ce problème revient, dans un système réparti statique, à calculer un couplage maximal de ce graphe de manière répartie. Ce problème classique a de nombreuses applications dans différents protocoles réseaux et a été largement étudié dans la littérature, y compris de manière tolérante aux pannes.

En effet, la tolérance aux pannes (aussi appelées fautes) est une des préoccupations importantes de la communauté des systèmes répartis. C’est pourquoi de nombreuses techniques ont vu le jour pour permettre à un tel système de fonctionner malgré l’occurrence de fautes. Chaque technique (stabilisation, robustesse, confinement de fautes...) privilégie une définition particulière d’une faute et du concept de tolérance.

Dans ce stage, on se concentrera sur l’approche stabilisante. Dans cette dernière, on suppose que le système est atteint pendant un temps fini par un nombre quelconque de fautes transitoires (i.e. de durée finie). Le système doit alors retrouver de lui-même un comportement conforme à ses spécifications en un temps fini. Un tel système est dit auto-stabilisant. Il existe de nombreux algorithmes auto-stabilisants pour le mariage maximal dans les systèmes statiques.

Cependant, la dynamique et la mobilité des composants tendent à devenir la norme dans les systèmes répartis actuels. Ces contraintes requièrent de nouveaux modèles afin de prendre en compte les caractéristiques propres de ces systèmes comme la mobilité des composants. Ces dernières années, un modèle semble s’imposer pour l’étude des systèmes répartis dynamiques : les \em Time Varying Graphs (TVG). A notre connaissance, il n’existe pas de solutions réparties au problème du mariage maximal dans ce modèle.

Objectifs du stage

L’objectif global du stage est l’étude du mariage maximal auto-stabilisant dans les systèmes répartis dynamiques, plus spécifiquement dans le modèle des TVG. La première partie du stage consistera en une étude bibliographique concernant les TVG, le mariage maximal et l’auto-stabilisation. La suite du stage consistera en une étude algorithmique complète du problème. On se concentrera sur les points suivants :
- Spécification du mariage maximal dans le cadre dynamique.
- Ecriture, preuve et analyse d’un algorithme auto-stabilisant pour cette spécification dans le modèle des TVG.
- Caractérisation des hypothèses nécessaires sur la dynamique du système pour l’existence d’une solution auto-stabilisante au problème.