A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm

Abstract

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 +{\mathcal{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, $\mathcal{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.

14 pages; International conférence; Uniform self-stabilizing variant of the problem, 9th International Workshop on Distributed Algorithms (WDAG'95), Mont-Saint-Michel : France (1995)