A Uniform Self-Stabilizing Minimum Diameter Spanning Tree Algorithm

الأصل · EN

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 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Δ+ D² + n n) expected time, and uses O(n² n + n W) 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.