Space-Optimal Counting in Population Protocols [Extended Version]

International audienceIn this paper, we study the fundamental problem of counting, which consists in computingthe size of a system. We consider the distributed communication model of population protocols of finitestate, anonymous and asynchronous mobile devices (agents) communicating in pairs (according to afairness condition). This work significantly improves the previous results known for counting in thismodel, in terms of (exact) space complexity. We present, prove correct and analyze the time complexitiesof the first space-optimal protocols solving the problem for two classical types of fairness, global andweak. Both protocols require no initialization of the counted agents.The protocol designed for global fairness, surprisingly, uses only one bit of memory (two states) percounted agent. The protocol, functioning under weak fairness, requires the necessary log P bits (Pstates, per counted agent) to be able to count up to P agents. Interestingly, this protocol exploits theintriguing Gros sequence of natural numbers, which is also used in the solutions to the Chinese Ringsand the Hanoi Towers puzzles. The convergence time of the protocol is exponential, but we prove thatthis is necessary (within a constant factor) for obtaining a space-optimal and semi-uniform solution