Uniform Dynamic Self-Stabilizing Leader Election
Uniform Dynamic Self-Stabilizing Leader Election
复制标题
统一动态自稳定领导者选举
DOI：
10.1109/71.588622
复制
发表时间：
1997
期刊：
影响因子：
--
通讯作者：
S. Moran
中科院分区：
文献类型：
--
作者：
S. Dolev;A. Israeli;S. Moran
如果分布式系统可以在任何可能的全局状态下启动，那么它就是自稳定的。一旦启动，系统就会自行恢复一致性，无需任何外部干预。自稳定特性使系统能够容忍故障，其中处理器在一段时间内表现出错误行为，然后在任意状态下自发恢复。当一次恢复与下一次故障之间的中间时间足够长时，系统就会稳定下来。如果具有相同数量邻居的所有处理器都相同，则分布式系统是统一的。如果分布式系统能够容忍处理器和链路的添加或删除而不需要重新初始化，那么它就是动态的。在这项工作中，我们研究了读写原子性下领导者选举的统一动态自稳定协议。我们的协议使用随机化来打破对称性。当处理器数量未知时，领导者选举协议在 O(/spl Delta/D log n) 时间内稳定，否则在 O(/spl Delta/D) 时间内稳定。这里/spl Delta/表示节点的最大度数，D表示图的直径，n表示图中处理器的数量。我们引入了用于同步的自稳定协议，该协议被用作领导者选举算法的构建块。我们通过提出一个简单、统一、自稳定的排名协议来结束这项工作。
A distributed system is self-stabilizing if it can be started in any possible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabilization property makes the system tolerant to faults in which processors exhibit a faulty behavior for a while and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next faulty period is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbors are identical. A distributed system is dynamic if it can tolerate addition or deletion of processors and links without reinitialization. In this work, we study uniform dynamic self-stabilizing protocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stabilizes in O(/spl Delta/D log n) time when the number of the processors is unknown and O(/spl Delta/D), otherwise. Here /spl Delta/ denotes the maximal degree of a node, D denotes the diameter of the graph and n denotes the number of processors in the graph. We introduce self-stabilizing protocols for synchronization that are used as building blocks by the leader-election algorithm. We conclude this work by presenting a simple, uniform, self-stabilizing ranking protocol.