.png){kind=icon}
返回
Distributed Minimum Spanning Tree Maintenance for Transient Node Failures
.png){kind=icon}
PRE
AI
DOI：10.1109/TC.2010.228.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
In many network applications, the computation takes place on the minimum-cost spanning tree (MST) of the network G; unfortunately, a single link or node failure disconnects the tree. The ALL NODES REPLACEMENT (ANR) problem is the problem of precomputing, for each node u in G, the new MST should u fail. This problem has been extensively investigated for serial and parallel settings, and efficient solutions have been designed for those environments. The situation is surprisingly different in distributed settings. In fact, no distributed solution exists to date which performs better than the brute-force repeated application of MST construction. In this paper, we consider for the first time the problem of computing all the replacement minimum-cost spanning trees distributively. We design a solution protocol, and we prove that the total amount of communication exchanges taking place is O(n), each exchange using at most O(n) data items. Hence, the total amount of data items communicated during the computation (the data complexity) is O(n(2)). We also show how the simpler problem ALL EDGES REPLACEMENT (AER) dealing with single edge failures, which can be solved with the same costs using some existing techniques. Also for the AER problem, efficient solutions exist in the serial and parallel setting but, prior to this work, no distributed solution other than brute force was known.
Keyword:
Minimum spanning tree
replacement tree
node failure
distributed algorithms
期刊
IF:
3.8
论文数:
5.3K
被引数:
9.8K
机构
引用论文
.png){kind=icon}
分享收藏Genuinely multipoint temporal quantum correlations and universal measurement-based quantum computing
OAAI
OAAI分享收藏A Distributed Algorithm for Finding All Best Swap Edges of a Minimum-Diameter Spanning Tree寻找最小直径生成树的所有最佳交换边的分布式算法
OAAI
OAAI分享收藏分享收藏
查看更多内容