Schéma général auto-stabilisant et silencieux de constructions de type arbres couvrants

International audienceNous proposons un schéma général, appelé Scheme, qui calcule des structures de données de type arbres couvrants dans des réseaux quelconques. Scheme est auto-stabilisant, silencieux et malgré sa généralité, est aussi efficace. Il est écrit dans le modèle à mémoires localement partagées avec atomicité composite, et supposeun démon distribué inéquitable, l'hypothèse la plus faible concernant l'ordonnancement dans ce modèle. Son temps de stabilisation est d'au plus 4 nmax rondes, où nmax est le nombre maximum de processus dans une composante connexe. Nous montrons également des bornes supérieures polynomiales sur le temps de stabilisation en nombre de pas et de mouvements pour de grandes classes d'instances de l'algorithme Scheme. Nous illustrons la souplesse de notre approche en décrivant de telles instances résolvant des problèmes classiques tels que l'élection de leader et la construction d'arbres couvrants