Recherche
Plan |
|
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 |
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 :
|
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 :
|
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 :
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 |
|
|
Conférences internationales avec commité de lecture |
|
|
|
Conférences internationales francophones avec commité de lecture |
|
Fin |