Czerner, Philipp ;
Guttenberg, Roland ;
Helfrich, Martin ;
Esparza, Javier
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 𝒪(m ⋅ n² 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 𝒪(m) states that run in expected 𝒪(m⁷ ⋅ n²) 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.
BibTeX  Entry
@InProceedings{czerner_et_al:LIPIcs.SAND.2022.11,
author = {Czerner, Philipp and Guttenberg, Roland and Helfrich, Martin and Esparza, Javier},
title = {{Fast and Succinct Population Protocols for Presburger Arithmetic}},
booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)},
pages = {11:111:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772242},
ISSN = {18688969},
year = {2022},
volume = {221},
editor = {Aspnes, James and Michail, Othon},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15953},
URN = {urn:nbn:de:0030drops159535},
doi = {10.4230/LIPIcs.SAND.2022.11},
annote = {Keywords: population protocols, fast, succinct, population computers}
}
29.04.2022
Keywords: 

population protocols, fast, succinct, population computers 
Seminar: 

1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)

Issue date: 

2022 
Date of publication: 

29.04.2022 