An O(n)O(n)-time self-stabilizing leader election algorithm

A self-stabilizing asynchronous distributed leader election algorithm is presented. The algorithm works for any connected unoriented (bidirectional) network with unique IDs. The solution also constructs a BFS tree of the network rooted at the elected leader. The proposed solution is silent and works under the unfair daemon. The algorithm stabilizes in O(n)O(n) rounds, where n is the number of processes in the network.

► We give a self-stabilizing silent distributed algorithm for leader election.
► We use the composite model of atomicity. Each node sees itself and its neighbors.
► The basic technique is flooding, but the problem is getting rid of fictitious leaders.
► Time complexity of O(n)O(n) rounds is obtained.
► The algorithm works under the unfair daemon, and is simpler than previous algorithms.