Name
Abstract | ||
|---|---|---|
Population protocols PPs are a model of passive distributed systems in which a collection of finite-state mobile agents interact with each other to accomplish a common task. Unlike other works, which investigate their computation power, this paper throws light on an aspect of PPs as a model of chemical reactions. Motivated by the well-known BZ reaction that provides an autonomous chemical oscillator, we address the problem of autonomously generating an oscillatory execution from any initial configuration i.e., in a self-stabilizing manner. For deterministic PPs, we show that the self-stabilizing leader election SS-LE and the self-stabilizing oscillator problem SS-OSC are equivalent, in the sense that an SS-OSC 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 and 2 n states are necessary to create an oscillation 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 and analyze some randomized oscillatory PPs. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.ic.2016.12.002 | Inf. Comput. |
Keywords | DocType | Volume |
Autonomous systems,Leader election,Population protocols,Self-organization,Self-oscillation,Self-stabilization | Journal | 255 |
ISSN | Citations | PageRank |
0890-5401 | 1 | 0.35 |
References | Authors | |
12 | 5 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Colin Cooper | 1 | 287 | 30.73 |
| Anissa Lamani | 2 | 118 | 11.31 |
| Giovanni Viglietta | 3 | 164 | 19.82 |
| Masafumi Yamashita | 4 | 2064 | 241.75 |
| Yukiko Yamauchi | 5 | 196 | 23.91 |