TY - JOUR

T1 - Fast and succinct population protocols for Presburger arithmetic

AU - Czerner, Philipp

AU - Guttenberg, Roland

AU - Helfrich, Martin

AU - Esparza, Javier

N1 - Publisher Copyright:
© 2023 Elsevier Inc.

PY - 2024/3

Y1 - 2024/3

N2 - In their 2006 seminal paper in Distributed Computing, Angluin et al. present a construction that, given any Presburger predicate, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m runs in O(m⋅n2logn) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states is exponential in m. Blondin et al. presented at 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 generalization of population protocols, 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, outputs a leaderless population protocol that decides the predicate. The protocol for a predicate of size m runs in O(m⋅n2logn) expected number of interactions, which is almost optimal in n, the number of interacting agents. However, the number of states is exponential in m. Blondin et al. presented at 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 generalization of population protocols, 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=85175032892&partnerID=8YFLogxK

U2 - 10.1016/j.jcss.2023.103481

DO - 10.1016/j.jcss.2023.103481

M3 - Article

AN - SCOPUS:85175032892

SN - 0022-0000

VL - 140

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

M1 - 103481

ER -