Anonymous agents now count themselves on any graph with new protocol

Population protocols model distributed systems where anonymous agents interact in pairs to compute global properties. In this paper accepted to DISC 2026, Petra Berenbrink (Universität Hamburg), Robert Elsässer (University of Salzburg), Tom Friedetzky (Durham University), and colleagues tackle the fundamental problem of counting the number of agents—when those agents are arranged on an arbitrary graph, not just a complete network. The random scheduler picks an edge each step, and one of the two nodes is randomly declared initiator, which acts as the symmetry-breaking mechanism.

The main result is a counting protocol that uses only Õ(n) states per agent and stabilizes with high probability in O(B(G)·log²n + L(G)·log n) interactions, where B(G) is the broadcast time and L(G) is the load-balancing time of the communication graph. The protocol builds on two novel sub-protocols: one for sampling independent random bits (given the initiator/responder asymmetry) and one for approximating log n to within O(log log n) additive error using O(poly log n) states. The exact counting protocol requires a unique leader, but the sub-protocols do not. Crucially, none of the algorithms needs any information about the underlying graph—they work on any connected topology. The paper also proves impossibility results for terminating uniform protocols that compute graph-size properties, both with and without a leader, clarifying the fundamental limits of this model.