Technical Report CS0807

TR#:CS0807
Class:CS
Title: UNIFORM SELF-STABILIZING LEADER ELECTION. PART 1: COMPLETE GRAPH PROTOCOLS.
Authors: S. Dolev, A. Israeli and S. Moran
PDFCS0807.pdf
Abstract:

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.

CopyrightThe above paper is copyright by the Technion, Author(s), or others. Please contact the author(s) for more information

Remark: Any link to this technical report should be to this page (http://www.cs.technion.ac.il/users/wwwb/cgi-bin/tr-info.cgi/1994/CS/CS0807), rather than to the URL of the PDF files directly. The latter URLs may change without notice.

To the list of the CS technical reports of 1994
To the main CS technical reports page

Computer science department, Technion
admin