A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property

Lélia Blin 1, * Maria Gradinariu Potop-Butucaru 2, * Stephane Rovedakis 1, * Sébastien Tixeuil 3, 4, *
* Auteur correspondant
2 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
3 GRAND-LARGE - Global parallel and distributed computing
LRI - Laboratoire de Recherche en Informatique, LIFL - Laboratoire d'Informatique Fondamentale de Lille, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unified manner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known ap- proaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Second, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date.
Liste complète des métadonnées

Littérature citée [24 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00384041
Contributeur : Lélia Blin <>
Soumis le : jeudi 14 mai 2009 - 10:46:35
Dernière modification le : jeudi 11 janvier 2018 - 06:22:26
Document(s) archivé(s) le : jeudi 10 juin 2010 - 23:09:15

Fichiers

SS_LF-MST.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00384041, version 1
  • ARXIV : 0905.2287

Citation

Lélia Blin, Maria Gradinariu Potop-Butucaru, Stephane Rovedakis, Sébastien Tixeuil. A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-free Property. [Research Report] Université d'Evry Val d'Essonne. 2009. 〈inria-00384041〉

Partager

Métriques

Consultations de la notice

468

Téléchargements de fichiers

189