TY - GEN
T1 - Constructing self-stabilizing oscillators in population protocols
AU - Cooper, Colin
AU - Lamani, Anissa
AU - Viglietta, Giovanni
AU - Yamashita, Masafumi
AU - Yamauchi, Yukiko
N1 - Funding Information:
This work has been supported, in part, by a Grant-in-Aid for Scientific Research on Innovative Areas “Molecular Robotics” (No. 24104003 ) of the MEXT , Japan.
Publisher Copyright:
© Springer International Publishing Switzerland 2015.
PY - 2015
Y1 - 2015
N2 - 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 wellknown 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 (SSLE) 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.
AB - 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 wellknown 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 (SSLE) 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.
UR - http://www.scopus.com/inward/record.url?scp=84943603342&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84943603342&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-21741-3_13
DO - 10.1007/978-3-319-21741-3_13
M3 - Conference contribution
AN - SCOPUS:84943603342
SN - 9783319217406
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 187
EP - 200
BT - Stabilization, Safety and Security of Distributed Systems - 17th International Symposium, SSS 2015, Proceedings
A2 - Pelc, Andrzej
A2 - Schwarzmann, Alexander A.
PB - Springer Verlag
T2 - 17th International Symposium on Stabilization, Safety and Security of Distributed Systems, SSS 2015
Y2 - 18 August 2015 through 21 August 2015
ER -