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

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.

Pour en savoir plus :
Séminaires
Quantum at LRI
Calcul quantique
Tuesday 04 February 2020 - 09h00
Salle : 465 - PCRI-N
.............................................

Progressive Data Analysis: a new computation parad
Gestion de données du Web
Friday 24 January 2020 - 14h00
Salle : 435 - PCRI-N
Jean-Daniel Fekete .............................................

Jeux d’instructions : des extensions SIMD aux exte
Architectures parallèles
Tuesday 21 January 2020 - 10h30
Salle : 465 - PCRI-N
Daniel Etiemble .............................................

Forum dev-LRI
Tuesday 14 January 2020 - 14h00
Salle : 445 - PCRI-N
Erik Bray .............................................

La transformation du travail, un analyseur des tra
Wednesday 18 December 2019 - 10h00
Salle : 475 - PCRI-N
Raquel Becerril-Ortega .............................................