Evènement pour le groupe Algorithmique Distribuée


Date 2014-10-06  14:00-15:00
Titrek-Partitionnement auto-stabilisant 
RésuméLe k-partitionnement organise un réseau comme suit : ses nœuds sous répartis en sous-ensembles disjoints appelés grappes et pour chaque grappe, un nœud appelé tête est distingué, de sorte que chaque nœud d'une grappe est au plus à k sauts de la tête de grappe. Une application possible est de faire du routage hiérarchique en suivant des chemins entre les têtes de grappe pour l'acheminement de messages à travers le réseau. Ceci est particulièrement intéressant dans les réseaux à large échelle où la probabilité de panne est élevée. Les fautes transitoires sont des pannes non-définitives qui n'affectent que le contenu du réseau et non son code ou sa structure. Un algorithme est auto-stabilisant s'il garantit au système, une fois que les fautes transitoires cessent, de récupérer un fonctionnement normal, en temps fini et sans intervention extérieure. Dans cet exposé, nous considérerons le problème du k-partitionnement auto-stabilisant. Il faut noter que construire un k-partitionnement de taille minimum est un problème NP-difficile. Nous proposerons un algorithme auto-stabilisant de k-partitionnement et étudierons ses propriétés dans l'arbre, dans un graphe connexe et dans un graphe de disques unitaires. Cette dernière topologie est généralement utilisée pour modéliser des réseaux de capteurs sans fil. 
Lieu75 
OrateurYvan Rivierre, (LaBRI) 



Aucun document lié à cet événement.

Retour
Retour à l'index