2013/12/11 by Franck Butelle, Butelle, Franck, Christian Lavault +3
Computer Science · #Data Structures and Algorithms (cs.DS) #Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC) #cs.DC #cs.DS
paper · pdf · doi:10.48550/arxiv.1312.3303
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)
arxiv created 2013/12/11 · arxiv updated 2013/12/12
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Δ+\cal D2 + n loglog n) expected time, and uses O(n2log n + n log W) memory bits (where n is the order of the graph, Δ 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.