|Full text||Click to download.|
|Citation||In Proc. of the 10th International Conference On
Principles Of Distributed Systems, 2006
|Authors||Michael J. Fischer
This paper considers the self-stabilizing leader-election problem in a
model of interacting anonymous finite-state agents. Leader election
is a fundamental problem in distributed systems; many distributed
problems are easily solved with the help of a central coordinator.
Self-stabilizing algorithms do not require initialization in order to
operate correctly and can recover from transient faults that
obliterate all state information in the system. Anonymous
finite-state agents model systems of identical simple computational
nodes such as sensor networks and biological computers.
Self-stabilizing leader election is easily shown to be impossible in
such systems without additional structure.
An eventual leader detector $\Omega?$ is an oracle that eventually detects the presence or absence of a leader. With the help of $\Omega?$, uniform self-stabilizing leader election algorithms are presented for two natural classes of network graphs: complete graphs and rings. The first algorithm works under either a local or global fairness condition, whereas the second requires global fairness. With only local fairness, uniform self-stabilizing leader election in rings is impossible, even with the help of $\Omega?$.
Back to publications
Back to previous page