A New Self-Stabilizing Minimum Spanning Tree Construction with Loop-Free Property

作     者：Blin, Lelia Potop-Butucaru, Maria Rovedakis, Stephane Tixeuil, Sebastien 

作者机构：Univ Paris 06 Univ Evry Val Essonne Sorbonne Univ CNRSLIP6 UMR 7606 4 Pl Jussieu F-75005 Paris France Univ Paris 06 Sorbonne Univ CNRS LIP6 UMR 7606 4 Pl Jussieu F-75005 Paris France Conservatoire Natl Arts & Metiers CEDRIC Paris France Univ Paris 06 Sorbonne Univ Inst Univ France CNRSLIP6 UMR 7606 4 Pl Jussieu F-75005 Paris France 

出 版 物：《COMPUTER JOURNAL》 (计算机杂志)

年 卷 期：2016年第59卷第2期

页      面：225-243页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：French National Research Agency (ANR) project IRIS [ANR-11-INFR-016] 

主　　题：self-stabilizing algorithm loop-free property minimum spanning tree construction 

摘      要：The minimum spanning tree (MST) construction is a classical problem in Distributed Computing for creating a globally minimized structure distributedly. Self-stabilization is versatile technique for forward recovery that permits to handle any kind of transient faults in a unifiedmanner. The loop-free property provides interesting safety assurance in dynamic networks where edge-cost changes during operation of the protocol. We present a new self-stabilizing MST protocol that improves on previous known approaches in several ways. First, it makes fewer system hypotheses as the size of the network (or an upper bound on the size) need not be known to the participants. Secondly, it is loop-free in the sense that it guarantees that a spanning tree structure is always preserved while edge costs change dynamically and the protocol adjusts to a new MST. Finally, time complexity matches the best known results, while space complexity results show that this protocol is the most efficient to date.