  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 \geq n$ for $n \in \mathbb{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.
