Cet ouvrage et des milliers d'autres font partie de la bibliothèque YouScribe
Obtenez un accès à la bibliothèque pour les lire en ligne
En savoir plus

Partagez cette publication

Modele
Exclusion mutuelle
Election d’un chef
Autostabilisation :
de l’exclusion mutuelle sur un anneau
a l’election d’un chef sur un graphe quelconque
Jer^ ome Durand-Lose
Laboratoire d’Informatique Fondamentale d’Orleans,
Universite d’Orleans, Orleans, FRANCE
JIRC { 30 juin 2005 { Blois
Jer^ ome Durand-Lose AutostabilisationModele
Exclusion mutuelle
Election d’un chef
Introduction
Modele
Exclusion mutuelle
Jeton
Passage
Election d’un chef
Architecture
Correction
Convergence
Conclusion
Jer^ ome Durand-Lose AutostabilisationModele
Exclusion mutuelle
Election d’un chef
Plan
Introduction
Modele
Exclusion mutuelle
Jeton
Passage
Election d’un chef
Architecture
Correction
Convergence
Conclusion
Jer^ ome Durand-Lose AutostabilisationModele
Exclusion mutuelle
Election d’un chef
Cadre : Algorithmique distribuee
Reseau de processeurs / machines
Probleme panne passagere
(redemarrage d’une machine, corruption de donnees/messages,
deconnexion...)
but retour a la normale
Contrainte sans intervention lourde
(humaine, redemarrage du reseau...)
Jer^ ome Durand-Lose Autostabilisation
Modele
Exclusion mutuelle
Election d’un chef
Cadre : Algorithmique distribuee
Reseau de processeurs / machines
Probleme panne passagere
(redemarrage d’une machine, corruption de donnees/messages,
deconnexion...)
but retour a la normale
Contrainte sans intervention lourde
(humaine, redemarrage du reseau...)
autostabilisation
Jer^ ome Durand-Lose Autostabilisation
Modele
Exclusion mutuelle
Election d’un chef
Autostabilisation
Con gurations
6
8
con gurations <
legales
:
Temps
-
perturbation
Jer^ ome Durand-Lose AutostabilisationModele
Exclusion mutuelle
Election d’un chef
Autostabilisation
Con gurations
6
8
con gurations <
legales
:
Temps
-
perturbation retour a la normale
Jer^ ome Durand-Lose AutostabilisationModele
Exclusion mutuelle
Election d’un chef
Autostabilisation { plus formellement
P un paradigme
L une ensemble de con gurations legales
correction toute execution entrant dans une con guration legale
veri e P a partir de cet instant
convergence toute execution atteint une con guration legale en
temps ni
Jer^ ome Durand-Lose AutostabilisationModele
Exclusion mutuelle
Election d’un chef
Paradigmes couverts
Election d’un chef
Exclusion mutuelle
Synchronisation
PIF (propagation avec retour)
Avoir un arbre recouvrant
Nommer les processeurs
Engendrer un sens de la direction
. ..
Jer^ ome Durand-Lose Autostabilisation
Modele
Exclusion mutuelle
Election d’un chef
Paradigmes couverts
Election d’un chef
Exclusion mutuelle
Synchronisation
PIF (propagation avec retour)
Avoir un arbre recouvrant
Nommer les processeurs
Engendrer un sens de la direction
. ..
Jer^ ome Durand-Lose Autostabilisation