咨询与建议

看过本文的还看了

相关文献

该作者的其他文献

文献详情 >A New Self-Stabilizing Minimum... 收藏

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.

读者评论 与其他读者分享你的观点

用户名:未登录
我的评分