Constructing self-stabilizing oscillators in population protocols
| Autor: | Masafumi Yamashita, Yukiko Yamauchi, Colin Cooper, Anissa Lamani, Giovanni Viglietta |
|---|---|
| Rok vydání: | 2017 |
| Předmět: |
Leader election
education.field_of_study Computer science Distributed computing Population Self-stabilization 0102 computer and information sciences 02 engineering and technology Population protocol Topology 01 natural sciences Computer Science Applications Theoretical Computer Science Task (computing) Computational Theory and Mathematics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing education Protocol (object-oriented programming) Information Systems |
| Zdroj: | Information and Computation. 255:336-351 |
| ISSN: | 0890-5401 |
| DOI: | 10.1016/j.ic.2016.12.002 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect