Lecture Notes in Computer Science, 1995, Volume 972/1995, 288-302, DOI: 10.1007/BFb0022154

Deterministic, constant space, self-stabilizing leader election on uniform rings

Gene Itkis, Chengdian Lin and Janos Simon

View Related Documents

Abstract

Self-stabilizing leader election protocols elect a single processor, leader, even when initiated from an arbitrary (e.g. faulty) configuration. Deterministic self-stabilizing leader election is impossible even on rings, if the number of processors is composite, no matter what computational resources are available to the processors. Moreover, it remains impossible even if the number of processors is prime, but each processor has less than log(n –1) bits of memory and the ring is unidirectional (i.e. each processor sees only itself and its clockwise neighbor). We show, however, that the deterministic self-stabilizing leader election is possible even if the processors are of constant size if the rings are bi-directional. More precisely, we present a deterministic uniform and constant space leader election protocol for prime sized rings under a central demon.

Key words  Fault Tolerant - Finite Automata - Leader Election - Ring - Se If-Stabilization

Partially supported by Israeli Council for Higher Education.

Fulltext Preview

Image of the first page of the fulltext document