Constructing self-stabilizing oscillators in population protocols

Colin Cooper, Anissa Lamani, Giovanni Viglietta, Masafumi Yamashita, Yukiko Yamauchi

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)


We consider the population protocol (PP) model used to represent a collection of finite-state mobile agents that interact with each other to accomplish a common task. Motivated by the well-known BZ reaction, we address the problem of autonomously generating an oscillatory execution from any initial configuration (i.e., in a self-stabilizing manner). For deterministic PPs under a deterministic scheduler, we show that the self-stabilizing leader election (SS-LE) problem and the self-stabilizing oscillation (SS-OS) problem are equivalent, in the sense that an SS-OS protocol is constructible from a given SS-LE protocol, and vice versa, which unfortunately implies that (1) resorting to a leader is inevitable (although we seek a decentralized solution), (2) n states are necessary to create oscillations of amplitude n, where n is the number of agents (although we seek a memory-efficient solution). Aiming at reducing the space complexity, we present some deterministic oscillatory PPs under a uniform random scheduler.

Original languageEnglish
Pages (from-to)336-351
Number of pages16
JournalInformation and Computation
Publication statusPublished - Aug 2017

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics


Dive into the research topics of 'Constructing self-stabilizing oscillators in population protocols'. Together they form a unique fingerprint.

Cite this