Exact size counting in uniform population protocols in nearly logarithmic time

We study population protocols: networks of anonymous agents that interact under a scheduler that picks pairs of agents uniformly at random. The size counting problem is that of calculating the exact number $n$ of agents in the population, assuming no leader (each agent starts in the same state). We give the first protocol that solves this problem in sublinear time. The protocol converges in $O(\log n\log \log n)$ time and uses $O(n^{60})$ states ($O(1) + 60 \log n$bitsofmemoryperagent)withprobability$1-O(\frac{\log \log n}{n})$\mathrm{.}Thetimecomplexityisalso$O(\log n \log \log n)$ in expectation. The time to converge is also $O(\log n\log \log n)$ in expectation. Crucially, unlike most published protocols with $\omega (1)$ states, our protocol is uniform: it uses the same transition algorithm for any population size, so does not need an estimate of the population size to be embedded into the algorithm. A sub-protocol is the first uniform sublinear-time leader election population protocol, taking $O(\log n\log \log n)$ time and $O(n^{18})$ states. The state complexity of both the counting and leader election protocols can be reduced to $O(n^{30})$ and $O(n^9)$ respectively, while increasing the time to $O({\log }^{2}n)$.