Ranking Opinions with Few States in Population Protocols Conference: ACM Symposium on Principles of Distributed Computing; July 6–10, 2026; Egham, United Kingdom ACM Symposium on Principles of Distributed Computing (PODC ’26), July 6–10, 2026, Egham, United Kingdom DOI: 10.1145/3796701.3815913 ISBN: 979-8-4007-2512-8/26/07 CCS: Theory of computation Distributed computing models CCS: Computing methodologies Self-organization
Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid · 2026
Read Ranking Opinions with Few States in Population Protocols Conference: ACM Symposium on Principles of Distributed Computing; July 6–10, 2026; Egham, United Kingdom ACM Symposium on Principles of Distributed Computing (PODC ’26), July 6–10, 2026, Egham, United Kingdom DOI: 10.1145/3796701.3815913 ISBN: 979-8-4007-2512-8/26/07 CCS: Theory of computation Distributed computing models CCS: Computing methodologies Self-organization by Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-18707.txt.
Introduction
Breitkopf and three co-authors solve, in a May 2026 paper, relative majority in population protocols with k cubed states. Agents start with one of k opinions, and each must output the most supported color. Earlier bounds put state complexity between order k squared and order k to the seventh. Their CIRCLES protocol partitions agents into circular linked lists of decreasing sizes, with no two agents sharing a color in one circle. An extension solves relative majority, and a modified version ranks opinions with two times k to the fourth states.
Catalog record
| CREATOR | Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104890 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.18707
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Ranking Opinions with Few States in Population Protocols Conference: ACM Symposium on Principles of Distributed Computing; July 6–10, 2026; Egham, United Kingdom ACM Symposium on Principles of Distributed Computing (PODC ’26), July 6–10, 2026, Egham, United Kingdom DOI: 10.1145/3796701.3815913 ISBN: 979-8-4007-2512-8/26/07 CCS: Theory of computation Distributed computing models CCS: Computing methodologies Self-organization Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, Stefan Schmid Abstract . Population protocols are a model of distributed computing where n n agents, each a simple finite-state machine, interact in pairs to solve a common task against a (adversarial) interaction scheduler. This model was intensively studied in recent years; in particular, the problem of relative majority received much attention: Each agent starts with an input opinion (or color) out of k k possibilities, and the goal is for each agent to eventually output the color with the largest support in the population. Before our work, the state complexity (the minimum number of states required per agent) was only known to be between Ω ( k 2 ) \Omega(k^{2}) and O ( k 7 ) O(k^{7}) . Our main contribution is a population protocol that solves the relative majority problem with k 3 k^{3} states. We achieve this result with a new protocol called Circles . While prior approaches in the literature relied on duels of agents to find the majority color — an approach that proved effective for the case with two colors — Circles partitions the agents into circular linked lists of decreasing sizes, with the property that no two agents with the same initial color lie in the same circle. We show that Circles always correctly computes the desired structure against the most adversarial of schedulers (weakly fair). We then show that a trivial extension of Circles solves the relative majority problem. We extend our protocol to handle various tie-breaking mechanisms or to support the case where the agents do not share a prior ordering of the colors. Finally, we show that a modification of Circles solves the ranking problem with 2 ⋅ k 4 2\cdot k^{4} states, where each agent must output the rank of its initial color in the population. † † cc-license: by 1. Introduction Population protocols are a distributed computing model where a population of n finite-state agents interacts in a chaotic manner, updating their state according to a common protocol upon interacting with each other. Ever since their introduction in 2006 by Angluin et al. ( 7 ) , population protocols have been widely studied and have become a standard setting to model key aspects of distributed computing ( 3 ) . Initially used as an abstraction for passively mobile finite-state sensor networks ( 7 ) , population protocols features intriguing connections to natural processes ( 17 ) , and can be used to model certain chemical reactions ( 20 ) , dynamics in social groups or animal populations, or even gene regulatory networks ( 15 ) . The model further features connections to other theoretical models such as Petri nets, vector addition systems, semilinear sets and Presburger arithmetic ( 7 ) . Multiple problems have already been studied in this model, the most illustrative of which are the leader election and majority problem ( 23 ) . This paper focuses on two related problems in the population protocol model, relative majority and ranking . Both assume that initially every agent stores a color. Relative majority then asks for each agent to output the most popular color, i.e., the one with the largest initial support in the population. The ranking problem generalizes relative majority by asking each agent to output the position of its initial color ranked by popularity. Both problems are fundamental tasks in distributed computing ( 11 ) in order to ensure fault tolerance or to enable conflict resolution. The majority problem is also relevant outside computer science, with applications in physics, biology, statistics and sociology ( 13 ) . The ranking problem amounts to implementing a sorting algorithm in the population protocol model, which is a basic task in many subfields of computer science. We are particularly interested in the fundamental question of how many states a protocol requires to solve a given task: the state complexity. This question is of relevance as in practice, the number of states that can be used is severely limited ( 5 ) : tiny sensor nodes have a limited memory ( 7 ) , chemical applications ideally require a small number of chemical species involved in the reactions ( 18 ) , and in DNA implementations the risk of faulty behavior increases with the number of states ( 5 ) . 1.1. Related work The majority problem is one of the most studied problems in the population protocol model, along with leader election ( 23 ) . Majority is a special case of relative majority with two colors: the agents can have one of two colors as input and the goal is for each agent to output the color with the larger support in the population. There exists a simple protocol solving majority with only 4 states per agent, concurrently found in ( 21 ) and ( 25 ) ; this protocol is provably the best possible in terms of state complexity ( 4 ) . A lot of research focuses on the trade-off between time and state complexity ( 4 ; 1 ; 12 ; 2 ) . This culminated in a protocol with O(\log n) many states, solving majority in expected O(n\log n) interactions assuming in every step of the execution two agents interact uniformly at random. This protocol by 19 is optimal space-wise for protocols running in O(n\log n) time. A first study of multiple colors in a related model was conducted in 2015 by 27 . They give solutions for both relative majority and ranking. Their definition of the ranking problem differs from ours, as they require every agent to output the whole ranking, not just the position of its own color in the ranking. Their algorithms require an exponential number of states: O(k\cdot 2^{k}) states per agent for the relative majority problem and O(k\cdot k!) states for the ranking problem, where k is the number of possible colors. They show that this bound is tight for the ranking problem – intuitively, an agent of any color ( k many) should be able to output any possible ranking ( k! many). We note that the exponential state complexity of this protocol is not only implied by its output requirement, but also by its internal logic. The authors conjectured that also the bound on the state complexity of relative majority if tight. This conjecture was disproved in 2017 by Gąsieniec et al. ( 24 ) who first broke the exponential barrier and gave a protocol that solves the relative majority problem with O(k^{7}) states (or as frequently cited O(k^{6}) states in case the agents only have a binary output indicating whether their initial color is in relative majority). The protocol orchestrates a distributed tournament between colors: the initial colors of each agent are written in binary form and define a binary tournament tree according to the longest common prefix rule. The color that wins the tournament is