Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s) Parallel Systems
Algorithmes auto-stabilisant bavards
Lélia Blin

21 January 2014, 10:30 - 21 January 2014, 11:30
Salle/Bat : 465/PCRI-N
Contact :

Activités de recherche : Distributed algorithms

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.

Pour en savoir plus :
Séminaires
Heterogeneous Treatment Effects Estimation: When M
Automated Reasoning
Thursday 02 June 2022 - 10:30
Salle : 2011 - DIG-Moulon
Naoufal Acharki .............................................

Witness Generation for JSON Schema
Data-Centric Languages and Systems
Monday 30 May 2022 - 00:00
Salle : 455 - PCRI-N
Mohamed-Amine BAAZIZI .............................................

TUTORIAL CODALAB - Apprenez à organiser un challen
Wednesday 13 April 2022 - 00:00
Salle : 1 - DIG-Moulon
Adrien Pavao .............................................

Generative Neural Networks for Observational Causa
Automated Reasoning
Thursday 07 April 2022 - 10:30
Salle : 2011 - DIG-Moulon
Diviyan Kalainathan .............................................

Datamining in Epi- and Phylogenetics
Tuesday 15 March 2022 - 11:00
Salle : 455 - PCRI-N
Thomas Haschka .............................................