A Self-Stabilizing Leader Election Algorithm for Tree Graphs

We propose a self stabilizing algorithm (protocol) for leader election in a tree graph. We show the correctness of the proposed algorithm by using a new technique involving induction. 1 Introduction In a distributed system the computing elements or nodes exchange information only by message passing. Every node has a set of local variables whose contents specify the local state of the node. The state of the entire system, called the global state, is the union of the local states of all the nodes in the system. Each node is allowed to have only a partial view of the global state, and this depends on the connectivity of the system and the propagation delay of different messages. Yet, the objective in a distributed system is to arrive at a desirable global final state (legitimate state), defined by some invariance relation on the global state. Systems that reach the legitimate state starting from any arbitrary (possibly illegitimate) state in a finite number of steps are called self-stabil..