pith. sign in

arxiv: 2605.18707 · v1 · pith:FKJGK3KUnew · submitted 2026-05-18 · 💻 cs.DC

Ranking Opinions with Few States in Population Protocols

Tom-Lukas Breitkopf , Julien Dallot , Antoine El-Hayek , Stefan Schmid This is my paper

Pith reviewed 2026-05-20 07:54 UTC · model grok-4.3

classification 💻 cs.DC
keywords population protocolsrelative majoritystate complexitycircular linked listsopinion aggregationdistributed computingranking problem
0
0 comments X

The pith

A protocol called CIRCLES solves relative majority using k cubed states per agent in population protocols.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how simple finite-state agents can identify the most common opinion among k colors by forming circular linked lists of decreasing sizes. In these lists, no two agents with the same starting color share a circle, which lets the system isolate and compare group sizes even when an adversary controls the order of interactions. This matters because earlier solutions needed up to k to the seventh states while lower bounds suggested at least k squared were necessary. The same circular structure extends directly to output the full ranking of all colors by their support size.

Core claim

The CIRCLES protocol partitions agents into circular linked lists of decreasing sizes such that no two agents with the same initial color lie in the same circle; this structure is formed and stabilized against any weakly fair scheduler and directly yields the relative majority with k cubed states per agent, with a modification achieving the ranking problem in two times k to the fourth states.

What carries the argument

CIRCLES, the protocol that builds circular linked lists of decreasing sizes ensuring each list contains distinct initial colors to expose the largest group.

If this is right

  • The relative majority problem is solvable with k cubed states.
  • The protocol extends to arbitrary tie-breaking rules and to agents without a shared prior ordering of colors.
  • A variant of the same structure solves the full ranking problem with two times k to the fourth states.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The circular separation technique may apply to other population-protocol tasks that require identifying an extremal value without explicit counting.
  • Convergence speed under random rather than adversarial schedulers could be measured in simulations to assess practical runtime.
  • Similar list-based organizations might reduce state needs in related models such as chemical reaction networks or biological aggregation.

Load-bearing premise

The interaction scheduler is weakly fair, so every pair of agents interacts infinitely often and the circular lists can form and stabilize.

What would settle it

A concrete execution trace under a weakly fair scheduler in which the circular lists either place two agents of the same color together or cause agents to output an incorrect majority color for a known input distribution.

Figures

Figures reproduced from arXiv: 2605.18707 by Antoine El-Hayek, Julien Dallot, Stefan Schmid, Tom-Lukas Breitkopf.

Figure 1
Figure 1. Figure 1: A modulo range contains all numbers covered by a [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Example of Circles with 𝑘 = 5 colors and 𝑛 = 14 agents. Agents with the same input color are stacked vertically. Proof. We prove the following predicate 𝐻(𝑟) by induction on 𝑟 ∈ [0, 𝑞]: Ø 𝑝=1...𝑟 𝑓 (𝐺𝑝 ) ⊆ C (𝐻(𝑟)) The base case for 𝑟 = 0 is trivial. Let 𝑟 ∈ [0, 𝑞 − 1], we assume that 𝐻(𝑟) holds and show that 𝐻(𝑟 + 1) also holds. We define the subconfiguration C [𝑟 + 1] = C \ ∪𝑝=1...𝑟 𝑓 (𝐺𝑝 ). Case 1: ∪ 𝑞 … view at source ↗
read the original abstract

Population protocols are a model of distributed computing where $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$ 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 $\Omega(k^2)$ and $O(k^{7})$. Our main contribution is a population protocol that solves the relative majority problem with $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 \cdot k^4$ states, where each agent must output the rank of its initial color in the population.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript presents the CIRCLES population protocol for the relative majority problem in the standard population protocol model. With k^3 states per agent, CIRCLES partitions the n agents into circular linked lists of strictly decreasing lengths such that no two agents sharing the same initial color occupy the same circle. The protocol is claimed to reach and stabilize this configuration from any initial state under any weakly fair scheduler. A simple extension then lets every agent output the color with the largest support; further variants handle tie-breaking rules, unknown color orderings, and the full ranking problem with 2k^4 states.

Significance. If the correctness claims hold, the work improves the best-known upper bound on state complexity for relative majority from O(k^7) to O(k^3), a substantial asymptotic gain. The CIRCLES construction supplies a new structural primitive (decreasing-size circular lists with color-separation invariant) that may be reusable for other aggregation tasks in the population-protocol model.

major comments (2)
  1. [§4] §4 (CIRCLES protocol definition and stabilization argument): the central claim that the no-same-color invariant is reached and preserved against every weakly fair scheduler is load-bearing. The transition rules for list creation, pointer updates, and merging must be shown to force separation of same-color agents regardless of interaction order; the current sketch does not exhibit an explicit progress measure or invariant that rules out perpetual co-location under adversarial scheduling.
  2. [Theorem 5.1] Theorem 5.1 (relative-majority extension): once the CIRCLES structure stabilizes, the rule by which agents extract the majority color from the observed circle sizes is only sketched. A precise description of the local decision procedure and a proof that it correctly identifies the color with largest support are required to support the main result.
minor comments (2)
  1. [Abstract] The abstract states that CIRCLES works 'against the most adversarial of schedulers (weakly fair)' but does not define weak fairness in the manuscript; a one-sentence reminder of the definition would aid readability.
  2. [§3] Notation for circle sizes and pointer fields is introduced without a consolidated table; adding a small table of state components and their meanings would clarify the k^3-state encoding.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive feedback on our manuscript. We address each major comment below and will incorporate the suggested clarifications and expansions into the revised version to strengthen the presentation of the proofs.

read point-by-point responses

  1. Referee: [§4] §4 (CIRCLES protocol definition and stabilization argument): the central claim that the no-same-color invariant is reached and preserved against every weakly fair scheduler is load-bearing. The transition rules for list creation, pointer updates, and merging must be shown to force separation of same-color agents regardless of interaction order; the current sketch does not exhibit an explicit progress measure or invariant that rules out perpetual co-location under adversarial scheduling.

    Authors: We agree that the stabilization argument benefits from greater formality. In the revision we will augment §4 with an explicit lexicographic progress measure (number of same-color co-locations first, then total circle length) together with a case-by-case analysis of the list-creation, pointer-update and merge rules. This will show that every interaction either strictly decreases the measure or preserves the invariant while advancing toward separation, ruling out perpetual co-location under any weakly fair scheduler. revision: yes

  2. Referee: [Theorem 5.1] Theorem 5.1 (relative-majority extension): once the CIRCLES structure stabilizes, the rule by which agents extract the majority color from the observed circle sizes is only sketched. A precise description of the local decision procedure and a proof that it correctly identifies the color with largest support are required to support the main result.

    Authors: We acknowledge the need for a fully explicit statement. The revised manuscript will define the local decision rule precisely: after stabilization each agent outputs the color of the longest circle it participates in (with a fixed total order on colors to break ties). We will add a short lemma proving correctness by showing that the separation invariant forces the largest color class to occupy strictly longer circles than any smaller class, so the observed maximum length identifies the relative majority. revision: yes

Circularity Check

0 steps flagged

No circularity: CIRCLES protocol and correctness proof are self-contained

full rationale

The paper introduces an explicit new protocol CIRCLES whose state transitions construct circular linked lists with the stated separation invariant, then proves that this structure is reached and stabilized under any weakly fair scheduler before extending the construction to relative majority. No equations, parameters, or claims reduce the target output to a fitted input, self-referential definition, or load-bearing self-citation whose validity depends on the present result. The derivation is therefore independent of its own conclusions and rests on direct verification of the finite-state rules against the scheduler assumption.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard population protocol model and the weakly fair scheduler assumption; no free parameters or invented entities are introduced beyond the CIRCLES structure itself.

axioms (1)
  • domain assumption The scheduler is weakly fair (every pair interacts infinitely often).
    Invoked to guarantee that the circular lists form and the protocol stabilizes correctly.

pith-pipeline@v0.9.0 · 5841 in / 1141 out tokens · 48336 ms · 2026-05-20T07:54:22.464896+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

28 extracted references · 28 canonical work pages · 1 internal anchor

  1. [1]

    Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest

    work page

  2. [2]

    InProceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Philip N

    Time-Space Trade-offs in Population Protocols. InProceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Philip N. Klein (Ed.). SIAM, Barcelona, Spain, 2560–2579. doi:10.1137/1.9781611974782.169

    work page doi:10.1137/1.9781611974782.169 2017

  3. [3]

    Dan Alistarh, James Aspnes, and Rati Gelashvili. 2018. Space-Optimal Majority in Population Protocols. InProceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), Artur Czumaj (Ed.). SIAM, New Orleans, LA, USA, 2221–2239. doi:10.1137/1.9781611975031.144

    work page doi:10.1137/1.9781611975031.144 2018

  4. [4]

    Dan Alistarh, Krishnendu Chatterjee, Mehrdad Karrabi, and John Lazarsfeld. 2024. Game Dynamics and Equilibrium Computation in the Population Protocol Model. InProceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC 2024). ACM, New York, NY, USA, 40–49. doi:10.1145/3662158.3662768

    work page doi:10.1145/3662158.3662768 2024

  5. [5]

    Dan Alistarh and Rati Gelashvili. 2018. Recent Algorithmic Advances in Popu- lation Protocols.ACM SIGACT News49, 3 (2018), 63–73. doi:10.1145/3289137. 3289150

    work page doi:10.1145/3289137 2018

  6. [6]

    Dan Alistarh, Rati Gelashvili, and Milan Vojnović. 2015. Fast and Exact Majority in Population Protocols. InProceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC 2015). ACM, New York, NY, USA, 47–56. https: //doi.org/10.1145/2767386.2767429

    work page doi:10.1145/2767386.2767429 2015

  7. [7]

    Talley Amir, James Aspnes, Petra Berenbrink, Felix Biermeier, Christopher Hahn, Dominik Kaaser, and John Lazarsfeld. 2023. Fast Convergence of k-Opinion Undecided State Dynamics in the Population Protocol Model. InProceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC 2023). ACM, Orlando, FL, USA, 13–23. doi:10.1145/3583668.3594589

    work page doi:10.1145/3583668.3594589 2023

  8. [8]

    What cannot be computed locally! , booktitle =

    Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Per- alta. 2006. Computation in networks of passively mobile finite-state sensors. Distributed computing18, 4 (2006), 235–253. doi:10.1145/1011767.1011810

    work page doi:10.1145/1011767.1011810 2006

  9. [9]

    James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. 2016. Time and Space Optimal Counting in Population Protocols. InProceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016) (LIPIcs). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Madrid, Spain, 13:1–13:17. doi:10.4230/LIPICS.OPODIS.2016.13

    work page doi:10.4230/lipics.opodis.2016.13 2016

  10. [10]

    Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. 2022. Fast Consensus via the Unconstrained Undecided State Dynamics. InProceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, (SODA 2022). SIAM, Alexandria, VA, USA, 3417–3429. doi:10.1137/1.9781611977073.135

    work page doi:10.1137/1.9781611977073.135 2022

  11. [11]

    Gregor Bankhamer, Petra Berenbrink, Felix Biermeier, Robert Elsässer, Hamed Hosseinpour, Dominik Kaaser, and Peter Kling. 2022. Population Protocols for Exact Plurality Consensus: How a small chance of failure helps to eliminate insignificant opinions. InProceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022). ACM, Salerno...

    work page arXiv 2022

  12. [12]

    Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. 2015. Plurality consensus in the gossip model. In26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015). ACM, San Diego, USA, 371–390. doi:10.1137/1.9781611973730.27

    work page doi:10.1137/1.9781611973730.27 2015

  13. [13]

    Petra Berenbrink, Robert Elsässer, Tom Friedetzky, Dominik Kaaser, Peter Kling, and Tomasz Radzik. 2021. Time-space trade-offs in population protocols for the majority problem.Distributed Comput.34, 2 (2021), 91–111. doi:10.1007/S00446- 020-00385-0

    work page doi:10.1007/s00446- 2021

  14. [14]

    Petra Berenbrink, Tom Friedetzky, George Giakkoupis, and Peter Kling. 2016. Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. InProceedings of the 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Rome (Italy), 136:1–136:14. doi:10.4230/LIPICS.ICALP. 2016.136

    work page doi:10.4230/lipics.icalp 2016

  15. [15]

    Michael Blondin and François Ladouceur. 2023. Population Protocols with Unordered Data. InProceedings of the 50th International Colloquium on Au- tomata, Languages, and Programming, (ICALP 2023) (LIPIcs, Vol. 261). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Paderborn, Germany, 115:1–115:20. doi:10.4230/LIPICS.ICALP.2023.115

    work page doi:10.4230/lipics.icalp.2023.115 2023

  16. [16]

    Bower and Hamid Bolouri (Eds.)

    James M. Bower and Hamid Bolouri (Eds.). 2001.Computational Modeling of Genetic and Biochemical Networks. The MIT Press. doi:10.7551/mitpress/2018. 001.0001

    work page doi:10.7551/mitpress/2018 2001

  17. [17]

    Shukai Cai, Taisuke Izumi, and Koichi Wada. 2012. How to Prove Impossibility Under Global Fairness: On Space Complexity of Self-Stabilizing Leader Election on a Population Protocol Model.Theory Comput. Syst.50 (04 2012), 433–445. doi:10.1007/s00224-011-9313-z

    work page doi:10.1007/s00224-011-9313-z 2012

  18. [18]

    Luca Cardelli and Attila Csikász-Nagy. 2012. The cell cycle switch computes approximate majority.Scientific reports2, 1 (2012), 656–656

    work page 2012

  19. [19]

    Philipp Czerner, Javier Esparza, and Jérôme Leroux. 2023. Lower bounds on the state complexity of population protocols.Distributed computing36, 3 (2023), 209–218. doi:10.1007/S00446-023-00450-4

    work page doi:10.1007/s00446-023-00450-4 2023

  20. [20]

    David Doty. 2014. Timing in chemical reaction networks. In25th Annual ACM- SIAM Symposium on Discrete Algorithms (SODA 2014). Portland (USA), 772–784. doi:10.1137/1.9781611973402.57

    work page doi:10.1137/1.9781611973402.57 2014

  21. [21]

    Korhonen, A single-exponential time 2-approximation algorithm for treewidth, in: IEEE 62nd Annual Symposium on Foundations of Computer Science (FOCS 2021), 2022, pp

    David Doty, Mahsa Eftekhari, Leszek Gasieniec, Eric E. Severson, Przemyslaw Uznanski, and Grzegorz Stachowiak. 2021. A time and space optimal stable population protocol solving exact majority. In62nd IEEE Annual Symposium on Foundations of Computer Science, (FOCS 2021). IEEE, Denver, CO, USA, 1044–1055. doi:10.1109/FOCS52979.2021.00104

    work page doi:10.1109/focs52979.2021.00104 2021

  22. [22]

    Moez Draief and Milan Vojnović. 2012. Convergence Speed of Binary Interval Consensus.SIAM Journal on Control and Optimization50, 3 (2012), 1087–1109. doi:10.1137/110823018

    work page doi:10.1137/110823018 2012

  23. [23]

    Antoine El-Hayek, Robert Elsässer, and Stefan Schmid. 2025. An Almost Tight Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population Protocol Model. InProceedings of the ACM Symposium on Principles of Distributed Computing, (PODC 2025). ACM, Huatulco, Mexico, 532–540. doi:10. 1145/3732772.3733505

    work page arXiv 2025

  24. [24]

    Robert Elsässer and Tomasz Radzik. 2018. Recent Results in Population Protocols for Exact Majority and Leader Election. InThe Distributed Computing Column, Stefan Schmid (Ed.)

    work page 2018

  25. [25]

    Spirakis, and Grzegorz Stachowiak

    Leszek Gąsieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. 2017. Deterministic Population Protocols for Exact Majority and Plurality. InProceedings of the 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Madrid (Spain), 14:1–14:14. doi:10.4230/ LIPICS.OPODIS.2016.14

    work page 2017

  26. [26]

    Mertzios, Sotiris E

    George B. Mertzios, Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, and Paul G. Spirakis. 2017. Determining majority in networks with local interactions and very small local memory.Distributed Comput.30, 1 (2017), 1–16. doi:10.1007/ S00446-016-0277-8

    work page 2017

  27. [27]

    Emanuele Natale and Iliad Ramezani. 2019. On the Necessary Memory to Com- pute the Plurality in Multi-Agent Systems. InProceedings of the 11th International Conference on Algorithms and Complexity (CIAC 2019). Rome (Italy), 323–338. http://arxiv.org/abs/1901.06549

    work page internal anchor Pith review Pith/arXiv arXiv 2019

  28. [28]

    excess leaders

    Saber Salehkaleybar, Arsalan Sharif-Nassab, and S. Jamaloddin Golestani. 2015. Distributed Voting/Ranking With Optimal Number of States per Node.IEEE transactions on signal and information processing over networks1, 4 (2015), 259–267. doi:10.1109/TSIPN.2015.2477777 8 Missing Proof Details 8.1 Proof of Lemma 3.2 Proof. Each time a set 𝐺𝑝 is constructed (fo...

    work page doi:10.1109/tsipn.2015.2477777 2015