UNIFORM DYNAMIC SELF-STABILIZING LEADER ELECTION

A distributed system is self-stabilizing ii it can be started in any p ossible global state. Once started the system regains its consistency by itself, without any kind of outside intervention. The self-stabiliz ation 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 rec overy and the next faulty period is long enough, the system stabilizes . A distributed system is uniform if all processors with the same numb er of neighbors are identical. A distributed system is dynamic if it c an tolerate addition or deletion of processors and links without reini tialization. In this work, we study uniform dynamic self-stabilizing p rotocols for leader election under readwrite atomicity. Our protocols use randomization to break symmetry. The leader election protocol stab ilizes in O(Delta D log n) time when the number of the processors is u nknown and O(Delta D), otherwise. Here Delta denotes the maximal degre e of a node, D denotes the diameter of the graph and n denotes the num ber of processors in the graph. We introduce self-stabilizing protocol s for synchronization that are used as building blocks by the leader-e lection algorithm. We conclude this work by presenting a simple, unifo rm, self-stabilizing ranking protocol.