Technical Report CS0807

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 crash and then recover spontaneously in an arbitrary state. When the intermediate period in between one recovery and the next crash is long enough, the system stabilizes. A distributed system is uniform if all processors with the same number of neighbours are identical. In this work, we study uniform self-stabilizing protocols for leader election under read/write atomicity. Out protocols use randomization to break symmetry. We first introduce a novel technique called the sl-game method for analyzing the performance of randomized distributed protocols. Then, we present two protocols for the case where each processor in the system can communicate with all other processors and analyze their performance using the sl-game technique.