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

A Self-Stabilizing Leader Election Algorithm In Named Network

作　　者：林克旺[1] 

机构地区：[1]厦门大学计算机科学系,福建厦门361005

出　　处：《基建优化》2006年第4期60-64,共5页Optimization of Capital Construction

基　　金：国家自然科学基金资助(69383004);福建省自然科学基金资助(A0310007)

摘　　要：选举问题是分布式计算中的一个基本问题。它一直受到广泛关注,先后发表了一大批研究论文。但是,现有的研究较少涉及选举算法的自稳定性,已经提出的自稳定选举算法的性能还不能令人满意。针对两个经典的自稳定选举算法———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）.

关 键 词：选举问题 自稳定算法 命名网络 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]