2013 | OriginalPaper | Buchkapitel
Self-stabilizing Leader Election in Population Protocols over Arbitrary Communication Graphs
verfasst von : Joffroy Beauquier, Peva Blanchard, Janna Burman
Erschienen in: Principles of Distributed Systems
Verlag: Springer International Publishing
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
This paper considers the fundamental problem of
self-stabilizing leader election
(
$\mathcal{SSLE}$
) in the model of
population protocols
. In this model, an unknown number of asynchronous, anonymous and finite state mobile agents interact in pairs over a given communication graph.
$\mathcal{SSLE}$
has been shown to be impossible in the original model. This impossibility can been circumvented by a modular technique augmenting the system with an
oracle
- an external module abstracting the added assumption about the system. Fischer and Jiang have proposed solutions to
$\mathcal{SSLE}$
, for complete communication graphs and rings, using an oracle Ω?, called the
eventual leader detector
. In this work, we present a solution for arbitrary graphs, using a
composition
of two copies of Ω?. We also prove that the difficulty comes from the requirement of self-stabilization, by giving a solution without oracle for arbitrary graphs, when an uniform initialization is allowed. Finally, we prove that there is no self-stabilizing
implementation
of Ω? using
$\mathcal{SSLE}$
, in a sense we define precisely.