Fast and Succinct Population Protocols for Presburger Arithmetic

Abstract

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 $\mathcal{O}(m\cdot n^2\log n)$ expected number of interactions, which is almost optimal in $n$. However, the number of states of the protocol is exponential in $m$. 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 $\mathcal{O}(m)$ states that run in expected $\mathcal{O}(m^7\cdot n^2)$ interactions, optimal in $n$, for all inputs of size $\Omega (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.

arXiv comment58 pages, 7 figures, to be published in the Journal of Computer and System Sciences, Special Issue on SAND 2022