HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation

Stabilizing leader election in population protocols

Davide Canepa 1 Maria Gradinariu Potop-Butucaru 1
1 Regal - Large-Scale Distributed Systems and Applications
LIP6 - Laboratoire d'Informatique de Paris 6, Inria Paris-Rocquencourt
Abstract : In this paper we address the stabilizing leader election problem in the population protocols model augmented with oracles. Population protocols is a recent model of computation that captures the interactions of biological systems. In this model emergent global behavior is observed while anonymous finite-state agents(nodes) perform local peer interactions. Uniform self-stabilizing leader election is impossible in such systems without additional assumptions. Therefore, the classical model has been augmented with the eventual leader detector, Omega?, that eventually detects the presence or absence of a leader. In the augmented model several solutions for leader election in rings and complete networks have been proposed. In this work we extend the study to trees and arbitrary topologies. We propose deterministic and probabilistic solutions. All the proposed algorithms are memory optimal --- they need only one memory bit per agent. Additionally, we prove the necessity of the eventual leader detector even in environments helped by randomization.
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download

Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Wednesday, August 8, 2007 - 11:18:10 AM
Last modification on : Friday, January 21, 2022 - 3:22:14 AM
Long-term archiving on: : Tuesday, September 21, 2010 - 1:21:30 PM


Files produced by the author(s)


  • HAL Id : inria-00166632, version 2


Davide Canepa, Maria Gradinariu Potop-Butucaru. Stabilizing leader election in population protocols. [Research Report] RR-6269, INRIA. 2007, pp.17. ⟨inria-00166632v2⟩



Record views


Files downloads