Janna Burman,

University Paris-South 11 and LRI – Laboratoire de Recherche en Informatique, Orsay, France –

Abstract:

We consider the fundamental problem of self-stabilizing
leader election (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. 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 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.

 

Date: 2014-Jan-28     Time: 14:00:00     Room: 336

For more information: