Dans cette thèse, nous nous sommes intéressés au concept de stabilisation instantanée. Ainsi, nous avons tout d'abord proposé deux solutions instantanément stabilisantes au problème de parcours en profondeur pour des réseaux enracinés quelconques. Ces deux protocoles sont écrits dans le modèle à états et fonctionnent sous l'hypothèse d'un démon distribué inéquitable : le démon le plus général du modèle. Le premier est basé sur des listes d'identités. Le second utilise un principe de question/réponse pour remplacer les listes d'identités. Nous proposons ensuite deux applications instantanément stabilisantes obtenues à partir de nos deux protocoles de parcours en profondeur. Ces deux applications évaluent des propriétés globales sur le réseau. La première application permet de marquer les points d'articulation et les isthmes du réseau. La seconde application permet d'évaluer si un ensemble donné est un ensemble séparateur du réseau. Enfin, dans une dernière partie, nous adoptons une approche plus générale en étudiant un protocole efficace permettant de transformer semi-automatiquement des protocoles de service mono-initiateurs en protocoles instantanément stabilisants. Un protocole de parcours en profondeur et un protocole de construction d'arbre en largeur illustrent la facilité avec laquelle nous pouvons rendre instantanément stabilisants ce type protocole grâce à notre transformateur. Le protocole de parcours en profondeur est non seulement trivial à écrire mais les performances obtenues en font un compromis quasi idéal entre les protocoles à listes et à questions présentés précédemment. Enfin, grâce à une propriété de comptage due à notre transformateur, nous montrerons comment utiliser ce protocole de parcours pour résoudre en quelques lignes l'exclusion mutuelle de manière instantanément stabilisante.
| Identifer | oai:union.ndltd.org:CCSD/oai:tel.archives-ouvertes.fr:tel-00120382 |
| Date | 08 December 2006 |
| Creators | Devismes, Stéphane |
| Publisher | Université de Picardie Jules Verne |
| Source Sets | CCSD theses-EN-ligne, France |
| Language | French |
| Detected Language | French |
| Type | PhD thesis |
Page generated in 0.0021 seconds