Self-stabilizing minimum-degree spanning tree within one from the optimal degree

• Main Authors: Blin, L., Potop-Butucaru, M.G., Rovedakis, S.
• Format: Conference Proceeding
• Language: English
• Subjects: Ad hoc networks; Algorithm design and analysis; Bandwidth; Costs; Distributed algorithms; Message passing; Peer to peer computing; Telecommunication network reliability; Telecommunication traffic; Tree graphs
• ISSN: 1530-2075
• DOI: 10.1109/IPDPS.2009.5161042

We propose a self-stabilizing algorithm for constructing a Minimum-Degree Spanning Tree (MDST) in undirected networks. Starting from an arbitrary state, our algorithm is guaranteed to converge to a legitimate state describing a spanning tree whose maximum node degree is at most Delta*+ 1, where Delta* is the minimum possible maximum degree of a spanning tree of the network. To the best of our knowledge our algorithm is the first self-stabilizing solution for the construction of a minimum-degree spanning tree in undirected graphs. The algorithm uses only local communications (nodes interact only with the neighbors at one hop distance). Moreover, the algorithm is designed to work in any asynchronous message passing network with reliable FIFO channels. Additionally, we use a fine grained atomicity model (i.e. the send/receive atomicity). The time complexity of our solution is O(mn 2 log n) where m is the number of edges and n is the number of nodes. The memory complexity is O(delta log n) in the send-receive atomicity model (delta is the maximal degree of the network).