Self-Stabilizing Leader Election in Dynamic Networks

Document Type

Article

Publication Date

1-1-2017

Publication Title

Theory of Computing Systems

First page number:

1

Last page number:

71

Abstract

Two silent self-stabilizing asynchronous distributed algorithms are given for the leader election problem in a dynamic network with unique IDs. A leader is elected for each connected component of the network. A BFS DAG, rooted at the leader, is constructed in each component. The construction takes O(Diam) rounds, where Diam is the maximum diameter of any component. Both algorithms are self-stabilizing, silent, and work under the unfair daemon, but use one unbounded integer variable. Algorithm DLE selects an arbitrary process to be the leader of each component. Algorithm DLEND (Distributed Leader Election No Dithering) has the incumbency property and the no dithering property. If the configuration is legitimate and a topological fault occurs, each component will elect, if possible, an incumbent to be its leader, i.e., a process which was a leader before the fault. Furthermore, during this computation, no process will change its choice of leader more than once. © 2017 Springer Science+Business Media New York

Keywords

Leader election; Self-stabilization; Silent algorithm; Unfair daemon; Incumbency; Dithering

Language

english

Find It

UNLV article access

Find in your library

Share

COinS