分布式超级节点选举算法.pdfVIP

4 2011 ，47 （14） Computer Engineering and Applications 计算机工程与应用 分布式超级节点选举算法 1，2 1 杜丽娟 ，余镇危 DU Lijuan1，2 ，YU Zhenwei1 1.华北科技学院 电子信息工程系，北京 101601 2.中国矿业大学 机电学院，北京 100083 1.Department of Electronic Information Engineering ，North China Institute of Science and Technology ，Beijing 101601，China 2.College of Mechanical and Electronic Engineering ，China University of Mining Technology ，Beijing 100083，China DU Lijuan ，YU Zhenwei.Algorithm for distributed super-node election.Computer Engineering and Applications ，2011 ，47 （14）：4-6. Abstract ：In super-node-based distributed systems ，if super-node failures or temporarily leaves ，it is hoped that the most capa- ble node could be elected as new super-node in self-organization way.This paper presents distributed super-node election algo- rithm.It firstly constructs bottom spanning tree through process of flooding ，and then leaf nodes pass messages along this tree. Information about nodes and edges is contained in the messages ，which are used by root node to construct minimum span- ning tree （MST ）.At last ，root node selects the most capable node as new super-node and broadcasts election results along MST.The algorithm performance is analyzed and compared from aspects of communication complexity and time complexity. Key words ：distributed ；super-node ；leader electing ；spanning tree ；minimum spanning tree 摘 要：基于超级节点的分布式系统中，若超级节点失效或临时离开，希望系统能够自组织地选举出能力最强的节点作为新的超 级节点。提出分布式超级节点选举算法，通过洪泛过程构造底层的生成树，叶子节点沿此树进行消息的传递，消息中包含着关于 节点和边的信息，根节点根据这些信息构造最小生成树。根节点选出能力最强的节点作为超级节点，并沿着最小生成树广播选 举结果。对算法性能从通信复杂度和时间复杂度两方面进行了分析和比较。 关键词：分布式；超级节点；领导人选举；生成树；最小生成树 DOI ：10.3778/j.issn. 1002-8331.2011.14.002 文章编号：1002-8331（2011 ）14-0004-03 文献标识码：A 中图分类号：TP393 1 前言 或离开网络，并可能发生随机的故障与恢复，进程之间还存在 基于超级节点的自组织覆盖网络为构建分布式应用提供 消息丢失和消息延迟；领导人选举服务包括组维护、故障检测 [1]