一个基于命名网络的自稳定的选举算法

• 作者: 林克旺
• 来源期刊: 基建优化
• 学科: 工学
• 关键词: 选举问题 自稳定算法 命名网络
• 年，卷（期）: 2006,（4）
• 所属期刊栏目: 技术经济
• 页码范围: 60-64
• 页数: 5页
• 分类号: TP301
• 字数: 5710字
• 语种: 中文

摘要

选举问题是分布式计算中的一个基本问题.它一直受到广泛关注,先后发表了一大批研究论文.但是,现有的研究较少涉及选举算法的自稳定性,已经提出的自稳定选举算法的性能还不能令人满意.针对两个经典的自稳定选举算法--AG算法和DIM算法进行了分析.AG算法适用于命名网络,算法虽然简单,但算法需要假设网络的大小是已知的并且时间复杂度为O(n2),其中n表示网络结点数目.DIM算法虽不需要网络大小假设是已知的,但其时间复杂度仍然需要O(△Dlogn),其中△和D分别表示结点最大的度和树的深度.利用DIM算法的思想,在AG算法的基础上,提出了一个基于命名网络的自稳定选举算法.该算法不需要知道网络的大小,而且时间复杂度为O(δ)(δ为网络直径).

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	林克旺	厦门大学计算机科学系	1	2	1.0	1.0