Angluin et al. proved that population protocols compute exactly the
predicates definable in Presburger arithmetic (PA), the first-order theory of
addition. As part of this result, they presented a procedure that translates
any formula $\varphi$ of quantifier-free PA with remainder predicates (which
has the same expressive power as full PA) into a population protocol with
$2^O(poly(|\varphi|))$ states that computes $\varphi$. More precisely,
the number of states of the protocol is exponential in both the bit length of
the largest coefficient in the formula, and the number of nodes of its syntax
tree.
In this paper, we prove that every formula $\varphi$ of quantifier-free PA
with remainder predicates is computable by a leaderless population protocol
with $O(poly(|\varphi|))$ states. Our result shows that, contrary to the
case of time complexity, where protocols with leaders can be exponentially
faster than leaderless protocols, protocols with and without leaders have both
polynomial state complexity.
Our proof is based on several new constructions, which may be of independent
interest. Given a formula $\varphi$ of quantifier-free PA with remainder
predicates, a first construction produces a succinct protocol (with
$O(|\varphi|^3)$ leaders) that computes $\varphi$; this completes the work
initiated in STACS'18, where we constructed such protocols for a fragment of
PA. For large enough inputs, we can get rid of these leaders. If the input is
not large enough, then it is small, and we design another construction
producing a succinct protocol with one leader that computes $\varphi$. Our last
construction gets rid of this leader for small inputs.

- URL:
- http://arxiv.org/abs/1910.04600
- BibTeX key:
- blondin2019succinct
- search on:

There is no review or comment yet. You can write one!