A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm

We present a uniform self-stabilizing algorithm, which solves the problem of distribu-tively 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 unique naming protocol, and the second stage is a stabilizing MDST protocol, designed as a 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∆+D2 +n log log n) expected time, and uses O(n2 logn+n logW) memory bits (where n is the order of the graph, ∆ is the maximum degree of the network, 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.