21 January 2014, 10h30 - 21 January 2014, 11h30 Salle/Bat : 465/PCRI-N
Contact :
Activités de recherche : Algorithmique distribuée
Résumé :
Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité évidente. Ce séminaire traite de l’auto-stabilisation, une méthode qui vise à concevoir des algorithmes distribués se « réparant d’eux-même » en cas de pannes transitoires pouvant impliquer toute modification arbitraire de l’état des processus. Plusieurs paramètres peuvent être pris en compte pour mesurer l’efficacité d’un algorithme auto-stabilisant, dont en particulier le temps de convergence et la complexité mémoire. L’importance du temps de convergence vient de la nécessité évidente pour un système de retrouver le plus rapidement possible un état valide après une panne. La nécessité de minimiser la mémoire vient, d’une part, de l’importance grandissante de réseaux offrant des espaces mémoires restreints, comme par exemple certains réseaux de capteurs, et, d’autre part, de l’intérêt de minimiser à la fois l’échange et le stockage d’information afin de limiter les potentialités de corruption de cette information. Lors de ce séminaire, nous traiterons de la minimisation de la mémoire au travers d'un exemple, à savoir le problème de l’élection d’un leader. Une borne inférieure de Ω(log n) bits de mémoire par noeud a été établie par Dolev, Gouda et Schneider (1999) pour ce problème fondamental. Cette borne n'est toutefois valable que pour des algorithmes silencieux, c'est-à-dire des algorithmes dont les registres ne sont plus modifiés lorsque le système a rejoint un état légitime. Nous verrons que, si l'on autorise l’algorithme à rester bavard (non-silencieux) même après avoir rejoint un état légitime, alors l’espace mémoire peut être amélioré d’un facteur au moins exponentiel.