Evènement pour le groupe Algorithmique Distribuée


Date 2015-10-19  14:00-15:00
TitreAlgorithmes auto-stabilisants pour des paramètres de décomposition et de domination dans les graphes 
RésuméUn système distribué est dit auto-stabilisant s’il peut reprendre un comportement correct en un temps fini après l’occurrence de fautes et ce sans intervention extérieure. De ce fait, l’auto-stabilisation est une approche optimiste pour la tolérance aux fautes dans le sens où elle protège le système des fautes transitoires. Un algorithme auto-stabilisant peut être défini selon différents modèles de communication ainsi que différents modèles de calcul. En effet, prouver la convergence d'un algorithme auto-stabilisant se doit dêtre faite selon un démon/scheduler qui peut être centralisé ou distribué, équitable ou non. De de plus, la complexité de ces algorithmes peut se calculer selon différentes mesures : moves, steps ou rounds, chacune d'entre elles apportant une connaissance propre sur l'algorithme proposé. Cependant, réussir à borner l'ensemble de ces mesures n'est pas toujours trivial, en particulier pour les cas les plus généraux de démons. La littérature des algorithmes auto-stabilisants est très riches. Cependant, nous allons nous intéresser dans cet exposé aux algorithmes auto-stabilisants pour quelques paramètres de théorie des graphes. En particulier, nous nous focaliserons dans un premier temps sur des décompositions particulières des graphes : en triangles et en étoiles uniformes ainsi que des paramètres de domination. Nous nous attarderons par la suite sur les techniques de preuve de convergence utilisées pour ces algorithmes.  
Lieu178 
OrateurMohammed Haddad 
UrlUniversité Lyon 1 



Aucun document lié à cet événement.

Retour
Retour à l'index