A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm - Université Paris Nanterre Accéder directement au contenu
Communication Dans Un Congrès Lecture Notes in Computer Science Année : 1995

A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm

Résumé

We present a uniform self-stabilizing algorithm, which solves the problem of distributively finding a minimum diameter spanning tree of an arbitrary positively real-weighted graph. Our algorithm consists in two stages of stabilizing protocols. The first stage is a uniform randomized stabilizing {\em unique naming} protocol, and the second stage is a stabilizing {\em MDST} protocol, designed as a {\em fair composition} of Merlin--Segall's stabilizing protocol and a distributed deterministic stabilizing protocol solving the (MDST) problem. The resulting randomized distributed algorithm presented herein is a composition of the two stages; it stabilizes in $O(n\Delta+{\cal D}^2 + n \log\log n)$ expected time, and uses $O(n^2\log n + n \log W)$ memory bits (where $n$ is the order of the graph, $\Delta$ is the maximum degree of the network, $\cal D$ is the diameter in terms of hops, and $W$ is the largest edge weight). To our knowledge, our protocol is the very first distributed algorithm for the (MDST) problem. Moreover, it is fault-tolerant and works for any anonymous arbitrary network.
Fichier principal
Vignette du fichier
UssMDST.pdf (264.7 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00917298 , version 1 (11-12-2013)

Identifiants

Citer

Franck Butelle, Christian Lavault, Marc Bui. A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm. 9th International Workshop on Distributed Algorithms (WDAG'95), Sep 1995, Mont-Saint-Michel, France. p. 257--272. ⟨hal-00917298⟩
390 Consultations
274 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More