Search papers, labs, and topics across Lattice.
This paper addresses the challenge of counting agents in population protocols on graphs, where agents interact based on a random scheduler and lack identifiers. The authors develop a size counting protocol that operates with $\tilde O(n)$ states and stabilizes in $O(B(G) \cdot \log^2(n) + L(G) \cdot \log(n))$ interactions, leveraging novel techniques for independent random bit sampling and approximating $\log n$. Key findings include the ability to count without a unique leader and the establishment of impossibility results for uniform protocols in computing graph-size properties.
Counting agents in anonymous population protocols can be achieved efficiently without a unique leader, challenging previous assumptions about the necessity of identifiers.
We consider the problem of counting the number of agents in a population protocol where the agents are connected by an underlying graph $G=(V,E)$ with $|V|=n$ nodes. In each step, a random scheduler selects an edge uniformly at random, and the incident nodes make a state transition. As per standard assumptions, agents are identical and anonymous, that is, have no identifiers. To break symmetry, in each interaction one of the agents is declared as the initiator uniformly at random. Our size counting protocol uses $\tilde O(n)$ states and stabilizes in $O( B(G) \cdot \log^2(n) + L(G) \cdot \log(n))$ interactions with high probability, where $B(G)$ is the broadcast time and $L(G)$ is the load balancing time. Our protocol is based on novel protocols for sampling independent random bits (given that the scheduler determines an initiator and responder) and approximating $\log n$ up to an additive error of $O(\log \log n)$ with high probability. The latter uses $O(poly\log(n))$ states and $O(B(G)\cdot\log^2 n)$ interactions. Both results may be of independent interest. The main protocol for exact counting requires the presence of a unique leader, the other two do not. None of the protocols requires any knowledge about the graph $G$. We conclude with impossibility results for terminating uniform population protocols that compute graph-size properties (like counting nodes or determining parity) with and without a leader.
