Name
Abstract | ||
|---|---|---|
Population protocols are a well established model of distributed computation by mobile finitestate 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 is an element of 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. |
Year | DOI | Venue |
|---|---|---|
2018 | 10.4230/LIPIcs.STACS.2018.16 | Leibniz International Proceedings in Informatics |
Keywords | DocType | Volume |
Population Protocols,Presburger Arithmetic | Conference | 96 |
ISSN | Citations | PageRank |
1868-8969 | 1 | 0.36 |
References | Authors | |
0 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Michael Blondin | 1 | 27 | 9.06 |
| Javier Esparza | 2 | 770 | 60.33 |
| Stefan Jaax | 3 | 5 | 2.13 |