TY - GEN
T1 - Fast and Succinct Population Protocols for Presburger Arithmetic
AU - Czerner, Philipp
AU - Guttenberg, Roland
AU - Helfrich, Martin
AU - Esparza, Javier
N1 - Publisher Copyright:
© Philipp Czerner, Roland Guttenberg, Martin Helfrich, and Javier Esparza; licensed under Creative Commons License CC-BY 4.0
PY - 2022/4/1
Y1 - 2022/4/1
N2 - In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate as input, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m (when expressed as a Boolean combination of threshold and remainder predicates with coefficients in binary) runs in O(m · n2 log n) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states of the protocol is exponential in m. This is a problem for natural computing applications, where a state corresponds to a chemical species and it is difficult to implement protocols with many states. Blondin et al. described in STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with O(m) states that run in expected O(m7 · n2) interactions, optimal in n, for all inputs of size Ω(m). For this, we introduce population computers, a carefully crafted generalization of population protocols easier to program, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols.
AB - In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate as input, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m (when expressed as a Boolean combination of threshold and remainder predicates with coefficients in binary) runs in O(m · n2 log n) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states of the protocol is exponential in m. This is a problem for natural computing applications, where a state corresponds to a chemical species and it is difficult to implement protocols with many states. Blondin et al. described in STACS 2020 another construction that produces protocols with a polynomial number of states, but exponential expected number of interactions. We present a construction that produces protocols with O(m) states that run in expected O(m7 · n2) interactions, optimal in n, for all inputs of size Ω(m). For this, we introduce population computers, a carefully crafted generalization of population protocols easier to program, and show that our computers for Presburger predicates can be translated into fast and succinct population protocols.
KW - fast
KW - population computers
KW - population protocols
KW - succinct
UR - http://www.scopus.com/inward/record.url?scp=85130775093&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.SAND.2022.11
DO - 10.4230/LIPIcs.SAND.2022.11
M3 - Conference contribution
AN - SCOPUS:85130775093
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022
A2 - Aspnes, James
A2 - Michail, Othon
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 1st Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2022
Y2 - 28 March 2022 through 30 March 2022
ER -