Fast and succinct population protocols for Presburger arithmetic

• Published in: Journal of computer and system sciences 2024-03, Vol.140, p.103481, Article 103481
• Main Authors: Czerner, Philipp, Guttenberg, Roland, Helfrich, Martin, Esparza, Javier
• Format: Article
• Language: English
• Subjects: Fast; Population computers; Population protocols; Succinct
• ISSN: 0022-0000; 1090-2724
• DOI: 10.1016/j.jcss.2023.103481

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⋅n2log⁡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. 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 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.