Fault Tolerance on Improved Distributed Spanning Tree Structure

摘要：

To improve the fault tolerance of the distributed spanning tree (DST) structure, we present an improved DST structure through orderly storing the elements in groups. Further, we give a representative selection rule, and based on which the node arrival and departure algorithms are proposed to balance the distribution of representatives in the structure. The maximal difference of the probabilities of any node to be selected as representatives by other nodes in the groups within the same level is not more than 1/a (a-1). Finally, we discuss the fault tolerance on the improved DST structure in a random failures model and an adversarial failures model. The results show that the improved DST structure is high resilient to fault even if the failures are carefully targeted. At most O(flogN) nodes are lost when /nodes failed, and it is better than skip graph.

关键词： algorithm load balance overlay networks peer to peer

作者: Tiejun Wang Heng Liu Ming Sun Zhen Liu Mingtian Zhou

作者单位: School of Computer Science and Engineering University of Electronic Science and Technology of China Chengdu,Sichuan,China

会议类型: 国际会议

会议名称: The 2nd IEEE International Conference on Advanced Computer Control(第二届先进计算机控制国际会议 ICACC 2010)

会议地点: 沈阳

会议语种:英文

页码: 296-300

在线出版日期: 2010-03-27（万方平台首次上网日期，不代表论文的发表时间）