2026-08-17T10:15:43Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8511 2024-03-06T10:42:17Z ddc:004 open_access

Large Flocks of Small Birds: on the Minimal Size of Population Protocols Blondin, Michael Esparza, Javier Jaax, Stefan Population protocols Presburger arithmetic Population protocols are a well established model of distributed computation by mobile finite-state agents with very limited storage. A classical result establishes that population protocols compute exactly predicates definable in Presburger arithmetic. We initiate the study of the minimal amount of memory required to compute a given predicate as a function of its size. We present results on the predicates x >= n for n \in N, and more generally on the predicates corresponding to systems of linear inequalities. We show that they can be computed by protocols with O(log n) states (or, more generally, logarithmic in the coefficients of the predicate), and that, surprisingly, some families of predicates can be computed by protocols with O(log log n) states. We give essentially matching lower bounds for the class of 1-aware protocols. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Michael Blondin and Javier Esparza and Stefan Jaax 2018 Is Part Of LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2018.16 urn:nbn:de:0030-drops-85116 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.16 eng https://creativecommons.org/licenses/by/3.0/legalcode