Population Protocols over Ordered Agents
2026-05-11 • Distributed, Parallel, and Cluster Computing
Distributed, Parallel, and Cluster ComputingFormal Languages and Automata Theory
AI summaryⓘ
The authors study a type of distributed computing where many simple agents interact in pairs to reach a consensus, but with the twist that each agent has an order or ID that restricts which pairs can interact. They focus on how this ordering affects what kinds of languages or computations these systems can recognize, showing a precise connection to certain well-known language classes. They also analyze the complexity when more powerful ordering predicates are used and examine which protocols reliably reach consensus. Notably, they find that deciding consensus is undecidable in some ordered cases but can be decided under certain conditions.
population protocolsdistributed computationfinite-state agentsordered agentsimmediate observationstar-free languagestwo-variable first-order logicconsensus problemundecidabilityNSPACE
Authors
Michael Blondin, Michaël Cadilhac, Benjamin Courchesne, Lucie Guillou, Corto Mascle, Isa Vialard
Abstract
Population protocols are a distributed computation model in which a collection of anonymous, finite-state agents interact in randomly chosen pairs and update their states according to a fixed transition function. The computation is defined by the eventual stabilization of the population to a consensus that represents the output. In practice, it is natural to allow each agent to carry a unique identifier and compare it with that of another agent before interacting. We model this extension by having agents be totally ordered and interactions between two agents to be fireable only if their pair of identifiers falls in some condition set. For instance, $\mathsf{PP}[<]$ allows for two agents to interact only if the first one appears before the second one. We study population protocols over ordered agents $\mathsf{PP}[N]$ where $N$ is a set of predicates available to restrict transition firing. We also study $\textsf{IO-PP}[N]$, the immediate observation fragment of $\mathsf{PP}[N]$ where only one agent changes state per interaction. Our main result is that $\textsf{IO-PP}[<]$ recognizes exactly the unambiguous star-free languages, which admits many other characterizations, such as two-variable first-order logic or two-way deterministic partially-ordered automata. We also provide a logic and an automaton model that fits in $\mathsf{PP}[<]$. We further show that if the successor predicate appears in a set $N$ of $\mathsf{NSPACE}(n)$-computable predicates, then $\textsf{IO-PP}[N]=\mathsf{PP}[N]=\mathsf{NSPACE}(n)$. Finally, we investigate the problem of deciding whether a given population protocol always stabilizes to a consensus. While this problem is decidable for unordered population protocols, we show that this is undecidable already for $\mathsf{PP}[<]$ and $\textsf{IO-PP}[+1]$, but conditionally decidable for $\textsf{IO-PP}[<]$.