Recherche

  Plan

Thématiques actuelles
Thèse
Thématiques de la thèse
Publications

  Thématiques actuelles

Science et Yoga
Etat de l'art : Pendant des siècles, la transmission du Yoga, de ses postures et de leur effet a été essentiellement orale, de maître à élève. Le principe de l'enseignement était simple : le maître savait ce qui était bon pour l'élève et lui distillait son enseignement. De son côté, l'élève ne remettait jamais en cause l'enseignement de son maître et ne lui posait jamais de questions. Une des conséquences directe de cet enseignement est que les effets des postures n'ont pratiquement jamais été étudiés de façon scientifique et systématique. Quand l'enseignant déclare qu'une posture est très bonne pour la circulation sanguine, renforce le c\oe ur ou permet une bonne récupération après effort, c'est parce que un maître Indien le lui à dit. Personne ne pose de questions, et aucune expérimentation n'est envisagée. Scientifiquement, tout reste donc à faire.
Projet de recherche : Evaluation de l'effet thérapeutique du Yoga sur les dysménorrhée sévères primitives.

Pour en savoir plus, téléchargez l'avant projet : yogaEtDysmennorhee.pdf

  Thèse

Titre : Raffinements de l'auto-stabilisation
Résumé : Avec l'émergence des réseaux (informatiques, téléphoniques et autres), de nouveaux problèmes ont fait leur apparition. Les systèmes répartis ont été conçus pour les résoudre. Quand ils sont sujets à des défaillances qui modifient le contenu des mémoires de leurs divers composants, il est important que ces systèmes puissent retrouver au plus vite un état normal (c'est à dire converger). Les algorithmes auto-stabilisants offrent une telle garantie. Malheureusement, l'auto-stabilisation ne donne aucune assurance quant au temps qui s'écoule entre la perturbation du système et la convergence. En particulier, il peut être arbitrairement long. De plus, il est également possible qu'une défaillance partielle du réseau se propage à l'ensemble du système, colportant ainsi une erreur. D'où l'émergence de nouveaux concepts proches de l'auto-stabilisation qui, tout en assurant la convergence vers un état normal, proposent en plus une qualité de service. Nous les avons appelé les ``raffinements de l'auto-stabilisation''. Dans cette thèse, nous nous sommes attachés à présenter formellement différents raffinement de l'auto-stabilisation et à les illustrer par des exemples. La stabilisation proportionnelle assure que le temps qui s'écoule entre la fin des défaillances et la convergence est proportionnel au nombre effectif de défaillances frappant le système. La k-stabilisation permet un retour à la normale à condition qu'une partie seulement du système soit défaillante. La stabilisation k-proportionnelle combine les deux approches : elle permet un retour à la normal à condition qu'une partie seulement du système soit défaillante, ce retour se faisant alors en un temps proportionnel au nombre effectif de fautes ; enfin, la stabilisation anti-corruption permet un retour vers un état correct sans que les éléments corrompus du réseau diffusent leur fausses informations vers les éléments non corrompus.
Téléchargement, version Française : Raffinements de l'auto-stabilisation
Téléchargement, version Anglaise : Refinement of self-stabilization

  Thématiques de la Thèse

La k-stabilisation et les algorithmes time adaptifs n'en sont qu'à leur début. Nombre des problèmes auto-stabilisants n'ont pas encore de solutions corrigeant les pannes de manière rapide et efficace. En particulier, trois axes de recherche semblent prometteurs :

1.   Présentation générale du domaine
Les réseaux informatiques ont connu au cours des dix dernières années une très grande expansion. La taille d'internet double tous les neuf mois, le nombre d'utilisateur de téléphone portable croît sans cesse.

Une caractéristique de tels réseaux est la variété de leurs composants, qui diffèrent tant en rapidité qu'en fiabilité ou en potentiel. De plus, le réseau n'est pas géré par une seule autorité, mais par des milliers de gestionnaires, ayant des politiques et des moyens parfois différents.

Dans un tel environnement, les fautes sont inévitables. Leur détection et réparation peut alors être très coûteuse. Dans les cas extrêmes, elle peut provoquer la paralysie d'une grande partie du réseau. C'est pourquoi ont été introduits les protocoles auto-stabilisants : ils sont conçus pour permettre au réseau de retrouver un état de fonctionnement correct même après une corruption (défaillance) de ses composants.

Une des hypothèses de l'auto-stabilisation est que tout le réseau peut-être corrompu. Cette hypothèse, peu réaliste, rend le temps qui s'écoule entre la corruption et le retour à la normale très long. D'un autre côté, une simple faute peut se propager à une grande partie du réseau, si les mesures adéquates ne sont pas prises. Par exemple, le tristement célèbre crash d'``ARPANET'' a été provoqué par une faute qui, diffusant de fausses informations, s'est très largement répandue.

D'où l'émergence de deux nouvelles classes d'algorithmes, les protocoles k-stabilisants et ``time adaptif''. Tout comme les protocoles auto-stabilisants, ils sont conçus pour retrouver un état de fonctionnement correct après défaillance. Mais, sous l'hypothèse qu'une petite partie seulement du réseau est corrompu, ils assurent un rapide retour à la normale.

1.1.   Systèmes répartis
Un système réparti est un graphe permettant de modéliser un réseau. Chaque noeud du graphe représente un des éléments du réseau (ordinateur, téléphone, processus, ...) et les arrêtes du graphe correspondent aux liens de communication entre ses divers éléments.

Par rapport aux systèmes centralisés, les systèmes répartis permettent principalement un meilleur partage des ressources et une plus grande fiabilité. Pour réaliser différentes tâches sur les systèmes répartis tout en exploitant au mieux leurs avantages ont été conçus des algorithmes spécifiques, adaptés au contexte réparti : les algorithmes répartis.

Un algorithme réparti est une fonction associant un protocole à chacun des noeuds d'un système réparti. Exécutés simultanément par tous les noeuds, ces protocoles permettent au système de vérifier une propriété globale.

D'un point de vue opérationnel, les algorithmes répartis diffèrent des algorithmes centralisés par plusieurs aspects :

  • Non connaissance de l'état global : dans un système centralisé, le processeur exécutant un protocole connaît l'intégralité du système. Il peut donc faire des choix en utilisant cette connaissance. Dans un système réparti, chaque processeur n'a qu'une connaissance locale de l'état du système.
  • Absence d'horloge / non déterminisme : dans un système réparti, chaque processeur possède sa propre horloge. Les différences de vitesse des multiples composant induisent des comportements non prévisibles.
  • Possibilité de résistance aux pannes : dans le cas d'un algorithme centralisé, si le noeud central est défaillant, tout le système est paralysé. Dans un système réparti, la panne d'un ou plusieurs noeuds peut ne pas être irrémédiable.
C'est cette dernière propriété que nous allons plus amplement développer ici.

1.2.   Auto-stabilisation
Les algorithmes auto-stabilisants sont des algorithmes répartis ayant la propriété de retrouver un comportement correct après une corruption du réseau. De manière informelle, un algorithme est auto-stabilisant pour un problème P si quelque soit l'état initial du système, après un certain temps, l'algorithme vérifie la spécification de P. Cette propriété assure qu'après une corruption (l'état du réseau est alors quelconque), l'algorithme retrouvera un comportement global correct.

De manière formelle, un algorithme est auto-stabilisant pour P si il existe un ensemble L de configurations du système (appelées configurations légitimes) vérifiant :

  • Convergence : toute exécution de l'algorithme conduit vers une configuration appartenant à L
  • Correction : toute exécution dont la configuration initiale est dans L vérifie la propriété P
Ces deux propriétés assurent bien un retour vers un état correct, puisque partant d'une configuration quelconque, une exécution conduit vers une configuration légitime, à partir de laquelle la spécification P est vérifié.

1.3   Complexité de l'auto-stabilisation
La complexité des algorithmes répartis se mesure de diverses manières, notamment en comptant l'espace mémoire utilisé par chacun des processeurs, le nombre de messages échangés ou le temps qui s'écoule entre le début de l'exécution et le retour à un comportement correct (cette dernière mesure est appelée temps de convergence).

Pour un protocole, être auto-stabilisation est une propriété forte assurant aux systèmes répartis une grande fiabilité. En revanche, cela est coûteux, notamment le temps de convergence qui peut s'avérer long. De plus, ce coût est généralement indépendemment de la corruption du réseau. Dans certain cas, une simple faute peut se propager et étendre la corruption à d'autres processeurs. La convergence reste assurée, mais elle est longue. D'où l'émergence de nouveaux concepts : les raffinements de l'auto-stabilisation.

2.   Contributions
2.1.   k-stabilisation
La k-stabilisation a été définie et présentée pour la première fois dans [PODC'99]. L'idée de base de la k-stabilisation est d'obtenir des temps de convergence courts, en faisant l'hypothèse qu'une petite partie du réseau seulement est corrompue. Sur un réseau de taille n, un algorithme k-stabilisant tolère jusqu'à k fautes.

De manière formelle, un algorithme est k-stabilisant pour P si il existe deux ensembles L et K de configurations vérifiant :

  • Toute configuration de K est obtenue à partir d'une configuration de L en corrompant jusqu'à k processeurs (les configurations de K sont faiblement corrompues).
  • k-convergence : Toute exécution de l'algorithme partant d'une configuration de K conduit vers une configuration appartenant à L.
  • Correction : Toute exécution dont la configuration initiale est dans L vérifie la propriété P
K peut-être considéré comme un ensemble de configuration ``faiblement'' corrompu : parmi les n processeurs que compte le réseau, seuls k ont leurs valeurs modifiées par rapport à une configuration légitime.

L' intérêt des algorithmes k-stabilisant est d'avoir, dans le cas où un faible nombre de fautes frappe le réseau, un temps de convergence plus court que leur pendant auto-stabilisant. Par exemple, considérons le problème de l'exclusion mutuelle sur un anneau de taille n. Si k fautes frappent le réseau, ce problème admet une solution auto-stabilisante convergeant en k× n étapes, alors qu'un algorithmes k-stabilisant ([PODC'98]) résout le même problème en k2 étapes.

2.2.   Algorithmes proportionnels (ou ``time adaptif'')
Quand un petit nombre de faute frappe un réseau, la k-stabilisation assure une convergence plus rapide que l'auto-stabilisation, mais toujours proportionnelle à k. D'où l'émergence d'un nouveau concept : les algorithmes proportionnels, ou encore les algorithmes s'adaptant complètement au nombre de faute. Si le réseau est touché par f corruptions, son temps de convergence dépendra de f et non d'une constante k ou de la taille du réseau.

2.3.   Algorithmes anti-corruption
Quand un petit nombre de faute frappe un réseau, la k-stabilisation comme la stabilisation proportionnelle assurent la convergence, mais n'offrent aucune certitude quant aux processeurs non initialement corrompus. D'où l'émergence d'un nouveau concept : la stabilisation anti-corruption. Si certain processeurs d'un réseau sont corrompus, un algorithme anti-corruption assure que la convergence aura lieu sans propagation des corruptions.

3.   Cadre des publications
Dans un premier temps, nous avons étudié la possibilité de transformer des algorithmes centralisés en algorithmes répartis ([RenPar'9]). Puis, nous avons brièvement jeté les bases de la k-stabilisation en présentant un algorithme k-stabilisant pour le problème de l'exclusion mutuelle ([PODC'98]). Nous avons ensuite formalisé la k-stabilisation puis écrit un algorithme d'exclusion mutuelle à la foi proportionnel, auto-stabilisant et anti-corruption([PODC'99]). Il est à noter que si le concept de proportionnel était déjà défini, notre article présentait la première solution proportionnelle à un problème dynamique. Plus récemment, nous avons publié une solution proportionnelle au problème de l'exclusion mutuelle sur un anneau synchrone ([PDCS2000]).
4.   Perspectives
4.1. Composer des algorithmes proportionnels
A travers la littérature, il existe un grand nombre d'algorithmes permettant de créer des structures d'anneau sur des graphes quelconques. Certains d'entre eux sont auto-stabilisants. On peut alors les composer avec des algorithmes fonctionnant sur des anneaux. Cela permet de généraliser la solution d'un problème à un graphe quelconque. Il serait intéressant d'appliquer le même principe aux algorithmes proportionnels.

En particulier, la construction d'un arbre à partir d'un réseau quelconque est un problème qui connaît diverses solutions. Une fois que la structure est établie, on peut imaginer qu'une corruption de faible envergure soit détectable localement, et réparable de même. D'où la possibilité de résoudre la création d'un arbre à partir d'un graphe quelconque de manière proportionnelle. Composer un tel algorithme avec une des exclusions mutuelles proposées dans cette thèse permettrait sans doute d'obtenir une exclusion mutuelle proportionnelle sur un graphe quelconque.

4.2. Lever (partiellement) des résultats d'impossibilité
Pour un certain nombre de problèmes distribués, des résultats d'impossibilité ont été établis : il n'est pas possible de les résoudre de manière auto-stabilisante. Ces résultats sont en grande partie liés aux hypothèses très faibles requises par les systèmes auto-stabilisants, comme la possibilité d'une configuration initiale quelconque.

Les algorithmes k-stabilisants ou proportionnels font des hypothèses plus fortes, ce qui leur permet de ne pas être sujets aux mêmes difficultés.

Plus précisément, il est impossible de résoudre de manière auto-stabilisante le problème de l'exclusion mutuelle sur un anneau totalement anonyme. Ce résultat est lié à une possible symétrie parfaite des configurations initiales (une configuration de 2i processeurs dans laquelle les processeurs j et j+i ont exactement la même valeur est problématique). Restreindre l'ensemble des configurations initiales à celles faiblement corrompues peut permettre d'interdire les configurations symétriques. Par exemple, si les configurations ont la propriété de ne pas contenir deux processeurs ayant le même état, n/3 corruptions (avec n taille du réseau) ne permettent pas de créer une configuration symétrique. Cette caractéristique rend possible la conception d'un algorithme k-stabilisant solution de l'exclusion mutuelle sur un anneau totalement anonyme.

4.3. Généraliser les techniques anti-corruption
A travers nos travaux, nous avons présenté plusieurs techniques permettant d'obtenir des algorithmes anti-corruption et proportionnels. Ces techniques sont en général liées à la structure même du réseau, généralement un l'anneau. Il serait intéressant de les généraliser pour les rendre opérationnelles sur les réseaux ayant des structures autres.

En particulier, dans [PODC'99], la procédure TEST présenté dans nous a permis de détecter la véracité d'un prédicat parmi les prédécesseurs d'un processeur. Cette procédure est bloquante (elle nécessite peu de communication), auto-stabilisante quand elle n'est pas bloquée et anti-corruption, ces trois propriétés faisant d'elle un outil qu'il serait intéressant de pouvoir utiliser sur des structures autres que les anneaux. Malheureusement, la notion de prédécesseur n'est définie que sur des graphes particuliers, comme les chaînes ou les anneaux. Néanmoins, sur un graphe quelconque, on pourrait la généraliser en testant un prédicat sur le voisinage d'un processeur.

4.4. Implémentation réelle
Le temps mis par un système auto-stabilisant pour retrouver un état correct est généralement long. Aussi l'auto-stabilisation ne constitue par une solution satisfaisante aux problèmes que rencontre actuellement les réseaux. La k-stabilisation et l'anti-corruption apparaissent comme des alternatives offrant une bonne sécurité face à des défaillances de taille raisonnable, sans surcoût excessif. Une collaboration avec l'industrie pour rendre k-stabilisant et anti-corruptif certains protocoles de bas niveau est donc envisageable.

  Publications


Journaux de vulgarisation scientifique
La Recherche
Christophe Genolini
Le rêve d'un réseau anti-bug
La Recherche, pages 56-58, Novembre 2001

La Recherche
Christophe Genolini, Pierre Lescanne
Ces problèmes sans solution
La Recherche, Janvier 2002

Conférences internationales avec commité de lecture
PDCS2000
Christophe Genolini
Optimal k-Stabilization: the case of Synchronous Mutual Exclusion.
PDCS2000, pages 371-376, Novembre 2000

PODC99
Joffroy Beauquier Christophe Genolini Shay Kutten
Optimal Reactive k-Stabilization: the case of Mutual Exclusion
PODC'99, Proceedings of the 18th Annual ACM Symposium on Principes of Distributed Computing, pages 209-218, Mai 1999

PODC98
Joffroy Beauquier Christophe Genolini Shay Kutten
k-Stabilization of Reactive Tasks
PODC'99, Proceedings of the 17th Annual ACM Symposium on Principes of Distributed Computing, page 318, 1998 (brief announcement)

Conférences internationales francophones avec commité de lecture
RenPar'9
Christophe Genolini
Un algorithme réparti de partitionnement des graphes
RenPar'9, Lausanne, Suisse, Mai 1997

  Fin