摘要
选举问题是分布式计算中的一个基本问题。它一直受到广泛关注,先后发表了一大批研究论文。但是,现有的研究较少涉及选举算法的自稳定性,已经提出的自稳定选举算法的性能还不能令人满意。针对两个经典的自稳定选举算法———AG算法和DIM算法进行了分析。AG算法适用于命名网络,算法虽然简单,但算法需要假设网络的大小是已知的并且时间复杂度为O(n2),其中n表示网络结点数目。DIM算法虽不需要网络大小假设是已知的,但其时间复杂度仍然需要O(ΔDlogn),其中Δ和D分别表示结点最大的度和树的深度。利用DIM算法的思想,在AG算法的基础上,提出了一个基于命名网络的自稳定选举算法。该算法不需要知道网络的大小,而且时间复杂度为O(δ)(δ为网络直径)。
Leader election algorithm is a fundamental algorithms in distributed computing, which has been studied extensively, but less papers involve its self-stabilization, and existing self-stabilizing election algorithms don＇t perform well. We analyze two classical self- stabilizing leader election algorithms - AG algorithm and DIM algorithm. The former is for the ID- based network and simple, but it assumes having knowledge about the network＇s size and its time complexity is O（n^2）, where n denotes the number of nodes, Although the latter doesn＇t assume the network＇ s size, its time complexity is O（ΔDlogn ） yet, where A and D denote the maximal degree among all nodes nd depth of the tree respectively. We utilize the idea of DIM algorithm and propose a self- stabilizing leader election algorithm for the ID - base network. The new algorithm assumes no knowledge about the network＇s size and its time complexity is O（δ）（δ denotes the diameter of the network）.
出处
《基建优化》
2006年第4期60-64,共5页
Optimization of Capital Construction
基金
国家自然科学基金资助(69383004)
福建省自然科学基金资助(A0310007)
关键词
选举问题
自稳定算法
命名网络
leader election
self-stabilizing algorithm
named network
