We study the fundamental problem of counting,
which consists in computing the size of a system. The considered model
are population protocols, which is the model of finite state, anonymous and asynchronous
mobile devices (agents) communicating in pairs (according to a fairness condition).
We significantly improve the previous results known for counting in this model,
in terms of (exact) space complexity. Specifically, we give the first space optimal
protocols solving the problem for two classical types of fairness,
global and weak. Both protocols require no initialization of the counted
agents.
The protocol designed for global fairness, surprisingly, uses only one
bit of memory (two states) per counted agent. The protocol, functioning
under weak fairness, requires the necessary log P bits (P states, per
counted agent) to be able to count up to P agents. Interestingly, this protocol
exploits the intriguing Gros sequence of natural numbers, which is
also used in the solutions to the Chinese Rings and the Hanoi Towers
puzzles.