conference paper published yes Tom-Lukas Breitkopf author Julien Dallot author Antoine El-Hayek author 888a098e-fcac-11ee-aff7-d347be57b7250000-0003-4268-7368 Stefan Schmid author MoHe department GradSch department PODC: Symposium on Principles of Distributed Computing The design and evaluation of modern fully dynamic data structures project Static and Dynamic Hierarchical Graph Decompositions project Population protocols are a model of distributed computing where 𝑛 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 𝑘 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 Ω(𝑘 2 ) and𝑂(𝑘 7 ). Our main contribution is a population protocol that solves the relative majority problem with 𝑘 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 · 𝑘^4 states, where each agent must output the rank of its initial color in the population. https://research-explorer.ista.ac.at/download/22327/22353/2026_ACMPODC_Breitkopf.pdf application/pdfno Association for Computing Machinery2026Egham, United Kingdom eng 9798400725128 2605.1870710.1145/3796701.3815913 414 - 424 Breitkopf, Tom-Lukas, et al. “Ranking Opinions with Few States in Population Protocols.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2026, pp. 414–24, doi:<a href="https://doi.org/10.1145/3796701.3815913">10.1145/3796701.3815913</a>. T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 414–424. Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Ranking opinions with few states in population protocols. In: <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2026:414-424. doi:<a href="https://doi.org/10.1145/3796701.3815913">10.1145/3796701.3815913</a> Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. “Ranking Opinions with Few States in Population Protocols.” In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, 414–24. Association for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3796701.3815913">https://doi.org/10.1145/3796701.3815913</a>. T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Ranking opinions with few states in population protocols,” in <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 414–424. Breitkopf, T.-L., Dallot, J., El-Hayek, A., &#38; Schmid, S. (2026). Ranking opinions with few states in population protocols. In <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i> (pp. 414–424). Egham, United Kingdom: Association for Computing Machinery. <a href="https://doi.org/10.1145/3796701.3815913">https://doi.org/10.1145/3796701.3815913</a> Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2026. Ranking opinions with few states in population protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 414–424. 223272026-07-14T05:40:17Z2026-07-16T11:19:52Z