Fast and succinct population protocols for Presburger arithmetic

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 center dot n2log n) 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 center dot n2) interactions, optimal in n, for all inputs of size S2(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.(c) 2023 Elsevier Inc. All rights reserved.

Automated summary

This paper presents a construction method that produces population protocols with a small number of states, while achieving near-optimal expected number of interactions, for deciding Presburger predicates.