16 Septembre - 22 Septembre


Retour à la vue des calendrier
Mardi 17 Septembre
Heure: 12:30 - 13:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Algorithmes auto-stabilisants
Description: Lélia Blin Dans le contexte des réseaux à grande échelle, la prise en compte des pannes est une nécessité. L'auto-stabilisation est une approche algorithmique de la tolérance aux pannes dans les systèmes distribués dont le but est de gérer la corruption de la mémoire des processeurs dues à des pannes transitoires. Plusieurs paramètres caractérisent l'efficacité d'un algorithme auto-stabilisant, dont en particulier (1) le temps pris par le système pour retourner dans une configuration légale suite à une corruption arbitraire de la mémoire de ses processeurs, et (2) l'espace mémoire utilisé par les processeurs pour exécuter l'algorithme. La minimisation de l'espace mémoire est motivée pas de nombreux aspects : existence de réseaux (tels que les réseaux de capteurs) offrant des espaces mémoires limités, la minimisation des échanges de données entre processeurs voisins, la limitation du stockage d'information afin de pouvoir utiliser des techniques de redondance, etc. Ce séminaire présentera l'auto-stabilisation au travers deux grands problèmes classiques : la construction d'arbres couvrants, notamment d'arbres couvrants de poids minimum, et l'election d'un leader. Il présentera en particulier les liens entre auto-stabilisation et les techniques de décision distribuée, incluant le calcul de bornes inférieures sur l'espace mémoire nécessaire à la résolution par des algorithmes auto-stabilisants des problèmes susmentionnés.