Population Protocols on Graphs: A Hierarchy

Population protocols have been introduced as a model in which anonymous finite-state agents stably compute a predicate of the multiset of their inputs via interactions by pairs. In this paper, we consider population protocols acting on families of graphs, that is to say on particular topologies. Stably computable predicates on strings of size n correspond exactly to languages of NSPACE(n), that is to say to non-deterministic space of Turing machines. Stably computable predicates on cliques correspond to semi-linear predicates, namely exactly those definable in Presburger’s arithmetic. Furthermore, we exhibit a strict hierarchy in-between when considering graphs between strings and cliques.