  Population protocols are a fundamental model in distributed computing, where
many nodes with bounded memory and computational power have random pairwise
interactions over time. This model has been studied in a rich body of
literature aiming to understand the tradeoffs between the memory and time
needed to perform computational tasks.
  We study the population protocol model focusing on the communication
complexity needed to achieve consensus with high probability. When the number
of memory states is $s = O(\log \log{n})$, the best upper bound known was given
by a protocol with $O(n \log{n})$ communication, while the best lower bound was
$\Omega(n \log(n)/s)$ communication.
  We design a protocol that shows the lower bound is sharp. When each agent has
$s=O(\log{n}^{\theta})$ states of memory, with $\theta \in (0,1/2)$, consensus
can be reached in time $O(\log(n))$ with $O(n \log{(n)}/s)$ communications with
high probability.
