Ranking Opinions with Few States in Population Protocols Tom-Lukas Breitkopf
Julien Dallot
Technische Universität Berlin Berlin, Germany [email protected]
Technische Universität Berlin Berlin, Germany [email protected]
Antoine El-Hayek
Stefan Schmid
arXiv:2605.18707v1 [cs.DC] 18 May 2026
Institue of Science and Technology Austria Klosterneuburg, Austria [email protected]
Abstract 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.
CCS Concepts • Theory of computation → Distributed computing models; • Computing methodologies → Self-organization.
Keywords Population Protocols, Ranking, Relative Majority, Plurality Consensus ACM Reference Format: Tom-Lukas Breitkopf, Julien Dallot, Antoine El-Hayek, and Stefan Schmid. 2026. Ranking Opinions with Few States in Population Protocols. In ACM
This work is licensed under a Creative Commons Attribution 4.0 International License. PODC ’26, Egham, United Kingdom © 2026 Copyright held by the owner/author(s). ACM ISBN 979-8-4007-2512-8/26/07 https://doi.org/10.1145/3796701.3815913
Technische Universität Berlin Berlin, Germany [email protected] Symposium on Principles of Distributed Computing (PODC ’26), July 6–10, 2026, Egham, United Kingdom. ACM, New York, NY, USA, 18 pages. https: //doi.org/10.1145/3796701.3815913
1
Introduction
Population protocols are a distributed computing model where a population of 𝑛 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 [19], 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 [4]: 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 [4].
PODC ’26, July 6–10, 2026, Egham, United Kingdom
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 [5]. A lot of research focuses on the trade-off between time and state complexity [1, 2, 5, 12]. This culminated in a protocol with 𝑂 (log 𝑛) many states, solving majority in expected 𝑂 (𝑛 log 𝑛) interactions assuming in every step of the execution two agents interact uniformly at random. This protocol by Doty et al. [20] is optimal space-wise for protocols running in 𝑂 (𝑛 log 𝑛) time. A first study of multiple colors in a related model was conducted in 2015 by Salehkaleybar et al. [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: 𝑂 (𝑘 · 2𝑘 ) states per agent for the relative majority problem and 𝑂 (𝑘 · 𝑘!) states for the ranking problem, where 𝑘 is the number of possible colors. They show that this bound is tight for the ranking problem – intuitively, an agent of any color (𝑘 many) should be able to output any possible ranking (𝑘! 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 𝑂 (𝑘 7 ) states (or as frequently cited 𝑂 (𝑘 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 deemed to be the majority color. The above protocol relies on a hard-coded binary representation of the colors, which implies that the agents share a prior ordering on the colors. Motivated by biological use cases, Natale and Ramezani [26] proposed a modified model where no such prior ordering is known, allowing agents only to memorize colors and to compare them only for equality (a formal definition of a related model where agents are only able to store a single immutable color can be found in [14]). They proposed a protocol using 𝑂 (𝑘 11 ) states in the unordered model by combining the relative majority protocol of Gąsieniec et al. with another protocol to assign a numerical label to each color. Natale and Ramezani [26] also show that any protocol solving relative majority requires Ω(𝑘 2 ) states. Apart from the work listed above concerned with always-correct protocols, there is also research on protocols correctly converging with high probability. This relaxation allows providing protocols with 𝑂 (𝑘) to 𝑂 (𝑘 + log 𝑛) states, achieving different guarantees of validity depending on the initial bias between the majority opinion
Breitkopf, Dallot, El-Hayek and Schmid
Model
Reference
Ordered
Salehkaleybar et al. [27] (2015) Gąsieniec et al. [24] (2017) This work Best-known lower bound [26]
State comp. 𝑂 (𝑘 · 2𝑘 ) 𝑂 (𝑘 7 ) k3 Ω(𝑘 2 )
Unordered
Natale and Ramezani [26] (2019) This work
𝑂 (𝑘 11 ) O(k4 )
Table 1: Existing results on the state complexity to solve the relative majority problem with probability 1 and for 𝑘 colors. and the second most popular√︁opinion [6, 9, 10, 22]. The additive bias required is typically Ω( 𝑛 log 𝑛) which motivates us in the search for an always-correct protocol.
1.2
Our contribution
This work presents a new always-correct protocol, Circles, that can be adapted to solve both the relative majority and the ranking problems in the population protocol model. Unlike previous approaches for this problem [24, 26, 27], our protocol does not rely on pairwise duels between colors but rather on a novel way to structure the agents into circular linked lists, ensuring that the smallest lists contains colors with the greatest support. This approach enables us to improve upon the state of the art regarding the state complexity for both problems we consider. For relative majority, we achieve a state complexity of 𝑂 (𝑘 3 ) under a weakly-fair scheduler (see Definition 2.1): Theorem 1.1 (The Circles protocol and relative majority). The Circles protocol, which uses 𝑘 2 many states, denoted ⟨𝑖 | 𝑗⟩ for 𝑖, 𝑗 ∈ [𝑘], stabilizes under a weakly-fair scheduler. In the stable configuration, agents of the form ⟨𝑖 |𝑖⟩ exist if and only if 𝑖 is the majority color. Propagating the result to every agent can be achieved by adding one output variable to the protocol, for a total of 𝑘 3 states. For the ranking problem, we break the exponential barrier [27] and provide a protocol that uses 𝑂 (𝑘 4 ) under a globally fair scheduler (see Definition 2.2): Theorem 1.2. There is a protocol that solves the ranking problem in case of a globally fair scheduler, and uses 2 · 𝑘 4 many states. Previous results combined several sub-protocols in an intricate way. In contrast, the Circles protocol is surprisingly simple, making it easy to analyse and adapt to different use cases. In this work we not only use it to solve both the ranking problem and the relative majority problem, but also a variety of modifications of the relative majority problem, dropping the assumption that initially an ordering on the colors exists and handling ties in a number of different ways.
1.3
Organization
The remainder of this paper is structured as follows. In Section 2 we define the population protocol model, the relative majority problem in different versions and the ranking problem. In Section 3 we present our new protocol Circles adapted to solve relative majority and prove its correctness. In Section 4 we present how to adapt Circles to solve the relative majority problem while handling
Ranking Opinions with Few States in Population Protocols
ties in different ways. In Section 5 we show how to adapt Circles to the unordered data model, where the agents do not share a prior ordering of the colors. In Section 6 we show how to adapt Circles to solve the ranking problem, and in Section 7, we discuss the gap between the 𝑂 (𝑘 3 ) upper bound and Ω(𝑘 2 ) lower bound for the problem.
2
Model, Problems and Notations
We will now briefly introduce models and problems used within this work.
2.1
Models and Problems
The Population Protocol model. Unless stated otherwise, we use the standard notation from [7]. A population P consists of a set 𝐴 of 𝑛 agents and an irreflexive relation 𝐸 ⊆ 𝐴 × 𝐴. It can be seen as a directed interaction graph. In this work we only consider the complete interaction graph. When a population protocol A runs in a population P every agent 𝑎 ∈ 𝐴 is in one state of a finite set of states. The input function maps an agents input, taken from some finite input set, to an initial state. In this work we always consider an input set of 𝑘 colors. After the initialization, pairs of agents interact. The agents have distinct roles when they interact, one is the initiator and the other is the responder. An interaction causes the initiator and the responder to update their states according to the transition function, which depends only on their previous states. Finally, the output of the population protocol is given by an output function which maps at any time an agent’s state to an output, taken from a finite output set. A configuration captures the “global state” of a population by assigning a state to each agent. Formally, a configuration can be fully described as a multiset of states. Similarly an input (or output) assignment maps an input (output) to every agent of the population. An interaction between two agents 𝑎, 𝑏 in configuration 𝑆 results (𝑎,𝑏 )
in a new configuration 𝑆 ′ , written as: 𝑆 −−−−→ 𝑆 ′ . Configuration 𝑆 ′′ is reachable from 𝑆 if there is some sequence of interactions, such that a population starting in 𝑆 undergoing the interaction sequence results in 𝑆 ′′ . We write this as 𝑆 → 𝑆 ′′ . A computation of a protocol is an infinite fair sequence of interactions. Which two agents interact in each step is determined by a scheduler. We introduce two different schedulers formalizing two different notions of fairness as done in other work [8, 26]. Definition 2.1 (Weakly Fair Scheduler). In a computation under a weakly fair scheduler every pair of agents interacts infinitely often. Definition 2.2 (Globally Fair Scheduler). In a computation under a globally fair scheduler for any two configurations 𝑆 and 𝑆 ′ with 𝑆 → 𝑆 ′ it holds that if 𝑆 occurs infinitely often in the computation, then 𝑆 ′ also occurs infinitely often. A computation stabilizes to some output assignment when no future interaction can change the output of any agent. The Unordered Data model. In the unordered data model, we assume that the agents do not agree on a prior ordering of the input colors: The agents can only compare their inputs for equality and
PODC ’26, July 6–10, 2026, Egham, United Kingdom
memorize colors. This setting was first used in [26] and a related version later formalized in [14]. Problems. In the literature the relative majority problem is also referred to as plurality, majority consensus or proportionate agreement [11]. The input assignment assigns a color from {0, 1, . . . , 𝑘−1} to every agent. A protocol solving the problem must stabilize to an output assignment in which every agent indicates as output the color that has more supporters than any other. Different versions on how to handle ties will be introduced later. In the ranking problem, the input assignment gives each agent a color from {0, 1, . . . , 𝑘 − 1} as well. A protocol solving the problem must stabilize to an output assignment in which each agent indicates as output the position of its input color in a ranking of the colors: an agent with the plurality color as its initial color should output 1, an agent with the second most supported color should output 2, and so on.
2.2
Notations
We explain here the notations used throughout the paper. Proofs marked with ★ are deferred to the appendix. multisets. For sets 𝑆 and 𝑇 we write 𝑆𝑇 to denote the set of functions 𝑓 : 𝑇 → 𝑆. If 𝑇 is finite we call the elements of N𝑇 multisets over 𝑇 . In this paper, the subset ⊆, the union ∪ and the set subtraction \ operations are generalized to multisets: if 𝐴, 𝐵 ∈ N𝑇 are two multisets on 𝑇 , it holds that 𝐴 ⊆ 𝐵 if for all 𝑡 ∈ 𝑇 , 𝐴(𝑡) ≤ 𝐵(𝑡), we define 𝐴 ∪ 𝐵 as the multiset 𝐶 such that for all 𝑡 ∈ 𝑇 , 𝐶 (𝑡) = 𝐴(𝑡) + 𝐵(𝑡), we define 𝐴 \ 𝐵 as the multiset 𝐶 such that for all 𝑡 ∈ 𝑇 , 𝐶 (𝑡) = max(0, 𝐴(𝑡) − 𝐵(𝑡)). remainder. For 𝑥 ∈ Z and 𝑝 ∈ N∗ , we define 𝑥 mod 𝑝 as the remainder of the euclidean division of 𝑥 by 𝑝. Note that this is a number in N, not Z/𝑝Z. ranges. Let 𝑥, 𝑦 ∈ N such that 𝑥 ≤ 𝑦. [𝑥, 𝑦] denotes the set {𝑥, 𝑥 + 1, . . . , 𝑦 − 1, 𝑦}, and (𝑥, 𝑦) denotes the set {𝑥 + 1, 𝑥 + 2, . . . , 𝑦 − 2, 𝑦 − 1}. With [𝑦] we denote {0, 1, . . . , 𝑦}. modulo ranges. Let 𝑥, 𝑦 ∈ N. We define modulo ranges: [𝑥, 𝑦] 𝑝 denotes the set {𝑥 mod 𝑝, (𝑥 + 1) mod 𝑝, . . . , (𝑥 + (𝑦 − 𝑥) mod 𝑝) − 1) mod 𝑝, (𝑥 + (𝑦 − 𝑥) mod 𝑝) mod 𝑝}, and (𝑥, 𝑦)𝑝 denotes the set {(𝑥 + 1) mod 𝑝, (𝑥 + 2) mod 𝑝, . . . , (𝑥 + (𝑦 − 𝑥) mod 𝑝) − 2) mod 𝑝, (𝑥 + (𝑦 − 𝑥) mod 𝑝) − 1) mod 𝑝}. For instance, [2, 7] 10 = {2, 3, 4, 5, 6, 7} and (8, 3)10 = {9, 0, 1, 2}. We say that a modulo range [𝑥, 𝑦] 𝑝 is included in another one [𝑥 ′, 𝑦 ′ ] 𝑝 , denoted [𝑥, 𝑦] 𝑝 ⊆ [𝑥 ′, 𝑦 ′ ] 𝑝 if it is included in the settheoretic sense, with the extra condition: 𝑥 ≠ 𝑦 ′ or 𝑦 ≠ 𝑥 ′ . This is to avoid the corner case: [𝑎, 𝑎 + 1] 𝑝 ⊆ [𝑎 + 1, 𝑎] 𝑝 , see Figure 1 for an illustration. braket. We overload the braket notation, frequently used in quantum mechanics, to note ordered pairs. For 𝑖, 𝑗 ∈ N, we write ⟨𝑖 | 𝑗⟩ simply to distinguish the different roles of 𝑖 and 𝑗. For agents storing some pair ⟨𝑖 | 𝑗⟩, we say they store a braket and refer to their bra and their ket for 𝑖 and 𝑗 respectively.
PODC ’26, July 6–10, 2026, Egham, United Kingdom
8 7
9 0 1 6 5 4
Breitkopf, Dallot, El-Hayek and Schmid
3.2 2 3
Figure 1: A modulo range contains all numbers covered by a clockwise walk from the start to the end of the range around the modular clock. This figure depicts [7, 1] 10 .
3 Solving the Relative Majority Problem 3.1 Presentation of the protocol In this section we introduce our protocol that solves the relative majority problem and prove its correctness. We consider the set [0, 𝑘 − 1] of 𝑘 many colors and present below the Circles1 protocol. States: The set of states 𝑄 contains every triples (𝑖, 𝑗, 𝑜) ∈ [0, 𝑘 − 1] 3 . In the remainder of this paper we will use the braket notation ⟨𝑖 | 𝑗⟩ to refer to the first two numbers of the triple, bra refers to ⟨𝑖 | and ket refers to | 𝑗⟩, while out refers to 𝑜. Input: each agent is initialized with ⟨𝑖 |𝑖⟩ and out = 𝑖, where 𝑖 ∈ [0, 𝑘 − 1] is the input color of the agent. Output: return out Transition function: We define weights for each braket ⟨𝑖 | 𝑗⟩ as follows: ( 𝑘 if 𝑖 = 𝑗 𝑤 (⟨𝑖 | 𝑗⟩) = ( 𝑗 − 𝑖) mod 𝑘 otherwise Two agents 𝑎 and 𝑏 that interact perform two successive operations: (1) 𝑎 and 𝑏 exchange their kets in case doing so strictly decreases the minimum weight of their two brakets. (2) If exactly one of 𝑎 or 𝑏 is of the form ⟨𝑖 |𝑖⟩ for some 𝑖 ∈ [0, 𝑘 − 1], set out𝑎 = out𝑏 = 𝑖. The intuition of the protocol is depicted in Figure 2. Let’s assume in this paragraph, for the sake of intuition, that only one color is in relative majority. As shown in Figure 2, think of a population as stacks of colors with the height of each stack representing the number of agents supporting it. If one were to remove rows from the stacks bottom to top until only a single row is left, then that row would contain only the color in relative majority. This is roughly what our protocol is doing, though it does not actually remove rows. Instead, in a way, it organizes the agents of a row into a cyclic linked list (which we call circle) and does not let them escape from it anymore. The bra of an agent represents its original color, while the ket of the agent represents the next color in the circle. The minimizing operation in the transition function ensures that if an agent is linked to another one too far away in the circle, it can always correct itself by meeting the correct ket. It organizes agents into a circle that is as tightly packed as possible (with respect to the numerical representation of their color). Once no agents can be added anymore, the circle never changes. The procedure then continues for the remaining agents, until in the final circle only one agent is contained: one holding the majority opinion. 1We overload the notation slightly, and also refer by Circles the protocol that behaves
similarly but does not have an out entry. This is useful to use the protocol for other purposes than relative majority.
Proof of Correctness
We prove the protocol’s correctness in Theorems 3.4 and 3.5. We beforehand introduce Greedy Independent sets, a construction on the input colors used to prove the protocol’s correctness, as well as two necessary, fairly easy Lemmas 3.2 and 3.3. This is a formalisation of rows in Figure 2. Definition 3.1 (Greedy Independent Sets). Consider the multiset of input colors to our protocol. We partition this multiset into sets 𝐺 1, 𝐺 2, . . . , 𝐺𝑞 as follows: store in 𝐺 1 as many inputs as possible as long as 𝐺 1 does not contain two equal colors; then apply the same on the remaining inputs to obtain 𝐺 2 , and so on. We begin with this fairly straightforward observation: Lemma 3.2 (★). (Majority Color). Assume there exists a unique color 𝜇 in relative majority, then it holds that 𝐺𝑞 = {𝜇} and there is no 𝑗 ≠ 𝜇 and 𝑝 ∈ [1, 𝑞] such that 𝐺 𝑝 = { 𝑗 }. We then introduce the main invariant of Circles, which stems from the fact that agents only exchange kets. Lemma 3.3 (★). (Global Braket Invariant). In every configuration and for all 𝑖 ∈ [0, 𝑘 − 1], the number of bras ⟨𝑖 | and the number of kets |𝑖⟩ are equal. Theorem 3.4. (Stabilization). Running Circles, the agents exchange their kets a finite number of times. Proof. We call 𝜔 the smallest ordinal number greater than all the integers2 . We prove the claim by exhibiting a quantity that strictly decreases at each ket exchange. Given a configuration 𝐶, let 𝑤 1 (𝐶), 𝑤 2 (𝐶) . . . 𝑤𝑛 (𝐶) be the weights of all the brakets sorted in increasing order. Define 𝑔(𝐶) = 𝜔 𝑛−1 · 𝑤 1 (𝐶) + 𝜔 𝑛−2 · 𝑤 2 (𝐶) + · · · + 𝜔 · 𝑤𝑛−1 (𝐶) + 𝑤𝑛 (𝐶) Assume that two agents exchange their kets. Let 𝑝 be the lowest index such that 𝑤 𝑝 (𝐶) changes before and after the ket exchange. By design of the protocol, 𝑤 𝑝 (𝐶) strictly decreases. This implies that 𝑔 strictly decreases when two agents exchange their kets. As an ordinal number cannot decrease infinitely many times, the number of ket exchanges is therefore finite. □ Theorem 3.5. (Correctness). Assume that there exists a unique color 𝜇 in relative majority. In the Circles protocol, all agents eventually output 𝜇 under a weakly fair scheduler. We define the brakets associated with a Circle: Definition 3.6 (Circle Braket Sets). For a given greedy independent set 𝐺 𝑝 with 𝑝 ∈ [1, 𝑞] (Definition 3.1), let 𝑔0, 𝑔1, . . . , 𝑔𝑚 be the elements of 𝐺 𝑝 sorted in increasing order and define 𝑓 (𝐺 𝑝 ) = {⟨𝑔0 |𝑔1 ⟩ , ⟨𝑔1 |𝑔2 ⟩ , . . . , ⟨𝑔𝑚 |𝑔0 ⟩} Theorem 3.5 follows directly from the following lemma: Lemma 3.7. After Stabilization (Theorem 3.4), let C be the multiset of brakets of the agents. We have that: Ø C= 𝑓 (𝐺 𝑝 ) 𝑝=1...𝑞 2 For readers unfamiliar with ordinals, we recommend checking this wikipedia page,
or this 15-minute video, which contains all that is needed for our proofs.
Ranking Opinions with Few States in Population Protocols
𝐺5
0
𝐺4
0
𝐺3
0
𝐺2 𝐺1
PODC ’26, July 6–10, 2026, Egham, United Kingdom
⟨0|0⟩ 3
⟨0|0⟩
1
3
⟨0|0⟩
0
1
3
4
0
1
3
0
1
3
2
⟨0|0⟩ ⟨3|3⟩
⟨0|3⟩
⟨1|1⟩
⟨3|3⟩
⟨0|1⟩
⟨1|3⟩
⟨3|0⟩
⟨0|0⟩
⟨1|1⟩
⟨3|3⟩
⟨4|4⟩
⟨0|1⟩
⟨1|3⟩
⟨3|4⟩
⟨4|0⟩
4
⟨0|0⟩
⟨1|1⟩
⟨3|3⟩
⟨4|4⟩
⟨0|1⟩
⟨1|3⟩
⟨3|4⟩
⟨4|0⟩
4
0
1
3
4
0
1
3
4
2
⟨3|0⟩
2
(a) Input colors, partitioned into greedy independent (b) States at the start of the protocol’s execu- (c) States at stabilization: brakets form cirsets 𝐺 1 , . . . , 𝐺 5 . The color in relative majority is the tion: each agent holds a braket ⟨𝑖 |𝑖 ⟩ equal cles covering the greedy independent sets. only one remaining in the smallest set (here 0 in 𝐺 5 ). to its input color 𝑖.
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, 𝑞]: Ø 𝑓 (𝐺 𝑝 ) ⊆ C (𝐻 (𝑟 )) 𝑝=1...𝑟
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: ∪𝑝=𝑟 +1𝐺 𝑝 contains only elements from one color. Let 𝑖 be that color. Then for any other color 𝑗 ≠ 𝑖, there are at most 𝑟 many bras ⟨𝑗 | and as many kets | 𝑗⟩, which are all included in ∪𝑝=1...𝑟 𝑓 (𝐺 𝑝 ). Thus all agents in C [𝑟 + 1] are of the form ⟨𝑖 |𝑖⟩. Since {⟨𝑖 |𝑖⟩} = 𝑓 (𝐺𝑟 +1 ), we have ∪𝑝=1...𝑟 +1 𝑓 (𝐺 𝑝 ) ⊆ C. Case 2: There are at least two different colors in 𝐺𝑟 +1 . We note 𝑔0, 𝑔1, . . . , 𝑔𝑚 the elements of 𝐺𝑟 +1 sorted in increasing order. Let 𝑙 ∈ [0, 𝑚]. To lighten notations, we will mean 𝑙 + 𝑠 mod (𝑚 + 1) each time we write 𝑙 + 𝑠 in the remainder of this proof. We prove that, if there is no agent with braket ⟨𝑔𝑙 |𝑔𝑙+1 ⟩ in 𝐶 [𝑟 + 1], then there exist two agents whose interaction creates that braket, a contradiction with the stability hypothesis. First notice that ⟨𝑔𝑙 | and |𝑔𝑙+1 ⟩ are in C [𝑟 + 1]. Indeed, note that there are at least 𝑟 + 1 many ⟨𝑔𝑙 | and 𝑟 + 1 many ⟨𝑔𝑙+1 | in C, as there are at least 𝑟 + 1 many agents with color 𝑔𝑙 and 𝑔𝑙+1 initially. By Theorem 3.3, this means we have at least 𝑟 + 1 many |𝑔𝑙+1 ⟩ in C. Because each 𝑓𝑝 for 𝑝 ≤ 𝑟 contains exactly one ⟨𝑔𝑙 | and one |𝑔𝑙+1 ⟩, we have that both ⟨𝑔𝑙 | and |𝑔𝑙+1 ⟩ are in C [𝑟 + 1]. Assuming by contradiction that there is no agent with braket ⟨𝑔𝑙 |𝑔𝑙+1 ⟩ in C [𝑟 + 1], then there exists an agent with braket ⟨𝑔𝑙 | 𝑗⟩ and an agent with braket ⟨𝑖 |𝑔𝑙+1 ⟩ in C [𝑟 + 1] for some 𝑖 and 𝑗. We show that those two agents exchange their kets if they interact. Claim 1. 𝑖, 𝑗 ∉ (𝑔𝑙 , 𝑔𝑙+1 )𝑚 Proof. By contradiction, assume that 𝑖 is in (𝑔𝑙 , 𝑔𝑙+1 )𝑚 . A ⟨𝑖 | in C [𝑟 + 1] indicates that 𝑖 had initially at least 𝑟 + 1 agents supporting it, as by contradiction if it was not the case, all the bras ⟨𝑖 | would
have been in ∪𝑟𝑝=1 𝑓 (𝐺 𝑝 ). By construction of 𝐺𝑟 +1 , we must have that 𝑖 is in 𝐺𝑟 +1 , and thus, 𝑔𝑙 and 𝑔𝑙+1 are not consecutive in the ordered list of 𝐺𝑟 +1 , a contradiction. The case 𝑗 ∈ (𝑔𝑙 , 𝑔𝑙+1 )𝑚 is symmetric. □ If 𝑖 ≠ 𝑔𝑙+1 , it holds by Claim 1 that 𝑤 (⟨𝑔𝑙 |𝑔𝑙+1 ⟩) = (𝑔𝑙+1 − 𝑔𝑙 ) mod 𝑘 < (𝑔𝑙+1 − 𝑖) mod 𝑘 = 𝑤 (⟨𝑖 |𝑔𝑙+1 ⟩) Otherwise, if 𝑖 = 𝑔𝑙+1 : 𝑤 (⟨𝑔𝑙 |𝑔𝑙+1 ⟩) = (𝑔𝑙+1 − 𝑔𝑙 ) mod 𝑘 < 𝑘 = 𝑤 (⟨𝑖 |𝑔𝑙+1 ⟩) Similarly, if 𝑗 ≠ 𝑔𝑙 , it holds by Claim 1 that 𝑤 (⟨𝑔𝑙 |𝑔𝑙+1 ⟩) = (𝑔𝑙+1 − 𝑔𝑙 ) mod 𝑘 < ( 𝑗 − 𝑔𝑙 ) mod 𝑘 = 𝑤 (⟨𝑔𝑙 | 𝑗⟩) Otherwise, if 𝑗 = 𝑔𝑙 : 𝑤 (⟨𝑔𝑙 |𝑔𝑙+1 ⟩) = (𝑔𝑙+1 − 𝑔𝑙 ) mod 𝑘 < 𝑘 = 𝑤 (⟨𝑔𝑙 | 𝑗⟩) Which proves that exchanging kets between ⟨𝑔𝑙 | 𝑗⟩ and ⟨𝑖 |𝑔𝑙+1 ⟩ reduces the minimum weight. An interaction between the two agents eventually happens as the scheduler is weakly fair, this interaction would therefore trigger a ket exchange, which is in contradiction with the stability hypothesis: we deduce that ⟨𝑔𝑙 |𝑔𝑙+1 ⟩ ∈ C [𝑟 + 1], which implies 𝑓 (𝐺𝑟 +1 ) ⊆ C [𝑟 + 1] and therefore 𝐻 (𝑟 + 1) holds. We proved by induction that 𝐻 (𝑞) holds: Ø 𝑓 (𝐺 𝑝 ) ⊆ C 𝑝=1...𝑞
As | ∪𝑝=1...𝑞 𝑓 (𝐺 𝑝 )| = |C| we can rewrite 𝐻 (𝑞) as an equality and the claim holds. □ Proof of Theorem 3.5. By Lemma 3.7 and Lemma 3.2, after Stabilization (Theorem 3.4), since we assumed that there is only one majority color, there exists at least one agent in braket ⟨𝜇|𝜇⟩ and none in braket ⟨𝑗 | 𝑗⟩ for 𝑗 ≠ 𝜇. The agent(s) with braket ⟨𝜇|𝜇⟩ will transmit their output color 𝜇 to the rest of the population and the claim follows. The claim on the number of states needed is straightforward, as 3 numbers between 0 and 𝑘 − 1 are stored. In the case where agents
PODC ’26, July 6–10, 2026, Egham, United Kingdom
only need to output whether or not their color is the majority one, an extra bit needs to be stored to record that fact, and the ⟨𝑖 |𝑖⟩ agents need to flip it accordingly when meeting other agents. □ This yields the following theorem: Theorem 1.1 (The Circles protocol and relative majority). The Circles protocol, which uses 𝑘 2 many states, denoted ⟨𝑖 | 𝑗⟩ for 𝑖, 𝑗 ∈ [𝑘], stabilizes under a weakly-fair scheduler. In the stable configuration, agents of the form ⟨𝑖 |𝑖⟩ exist if and only if 𝑖 is the majority color. Propagating the result to every agent can be achieved by adding one output variable to the protocol, for a total of 𝑘 3 states. Note that before this last proof, at no point did we use the fact that there is only one majority color, and thus, we can use all the lemmas to analyze what happens in the case of ties, which we do in the following sections.
3.3
A note on the time complexity
While this paper focuses on the space complexity of the problem, it is worthwhile talking briefly about the time complexity of the problem, which is typically done under the random scheduler: where for each interaction, two agents are chosen uniformly at random. Before talking about the Circles protocol, let’s look at an intermediate result: Assume you have ℓ pairs of tokens on some agents that need to meet, in any order. Then in any interaction, the probability 2ℓ that one such pair is chosen is 𝑛 (𝑛−1) , and thus the expected time until one such pair being chosen is 𝑛 (𝑛−1) 2ℓ . Then there are only ℓ − 1 many pairs to interact. Thus, the total expected time for all pairs to Íℓ 𝑛 (𝑛−1) interact is 𝜆=1 = Θ(𝑛 2 log ℓ). 2𝜆 Now consider the Circles protocol. Assume for the moment that all opinions initially have the same number of agents. Then there are 𝑛 bra-ket pairs that need to meet before stabilisation, in any order. By the result above, this takes 𝑂 (𝑛 2 log 𝑛) time. If we remove the assumption that all opinions initially have the same number of agents, then order matters. Indeed, the circles with more agents need to have stabilised before circles with fewer agents can start pairing up. There are at most 𝑘 many different circles, and thus, the total running time is at most 𝑂 (𝑘𝑛 2 log 𝑛).
4
Tie Handling Mechanisms
In this section, we describe three different ways to handle ties in the relative majority problem.
4.1
Reporting Ties
We present the Circles_TieReport protocol which extends the Circles protocol and enables it to report if there is more than one color in relative majority, i.e. if there is a tie. Circles_TieReport solves a version of the relative majority problem where, in case of a tie, all the agents must return a specific value to indicate that there is a tie. This feature was present in the paper from Gąsieniec et al. [24] where the agents could keep track of a potential tie with the label zero. In case there is no tie, all the agents must still return the majority color. We add to the agents’ states a variable tie_state on top of the states of Circles. tie_state can have three values: no_tie, tie or tie_spreader. At the beginning, all the agents are at no_tie. Without
Breitkopf, Dallot, El-Hayek and Schmid
interfering, tie_state evolves in parallel of Circles and follows three rules. (1) tie detection. An agent ⟨𝑖 |𝑖⟩ that decays into ⟨𝑖 | 𝑗⟩ with 𝑖 ≠ 𝑗 goes to tie_spreader. (2) tie spreading. An agent at tie_spreader sets to tie any encountered agent ⟨𝑖 | 𝑗⟩ such that 𝑖 ≠ 𝑗. (3) tie correction. An agent ⟨𝑖 |𝑖⟩ sets any encountered agent to no_tie. The output changes as follows: • Agents in no_tie output the winning color stored in 𝑜𝑢𝑡 as usual (by default behavior of Circles). • Agents in tie or tie-spreader output “tie”. Theorem 4.1 (★). Circles_TieReport solves the relative majority problem, where all agents output the color of the majority if the majority is strict. If there is a tie, agents do not output a color, but rather report that there is a tie. It requires 3𝑘 3 many states, which can be reduced to 4𝑘 2 if agents are not required to output the majority color, but only whether their color wins or loses.
4.2
Sharing Ties
In this subsection we would like that, even in case of a tie, all agents with a winning color output their color. Agents with a losing color output any winning color. The Circles_TieSharing protocol is defined as follows: From the Circles, we keep everything apart from item (2) of the transition function (the one that updates the out of agents). We add a variable “status” that can have values winner_spreader, winner or loser. All agents start at winner. The variable status evolves in parallel of Circles and follows the following rules, where all brakets below are considered after the application of the transition rule (1) of Circles. (1) token generation: An agent that exchanged kets to become ⟨𝑖 | 𝑗⟩ with 𝑖 ≠ 𝑗 is set to winner_spreader. (2) token destructor: An agent ⟨𝑖 | 𝑗⟩ that recombines into ⟨𝑖 |𝑖⟩ is set to winner. (3) token destruction: An agent with braket ⟨𝑖 |𝑖⟩ sets agents at ⟨𝑖 | 𝑗⟩ to winner, otherwise sets agents at ⟨𝑖 ′ | 𝑗⟩ with 𝑖 ′ ∉ {𝑖, 𝑗 } to loser. (4) token multiplication: If 𝑎 with ⟨𝑖 | 𝑗⟩ at winner_spreader meets 𝑏 at loser with ⟨𝑗 | 𝑗 ′ ⟩, set 𝑏 to winner_spreader. (5) token ascent: If an agent 𝑎 with ⟨𝑖 | 𝑗⟩ at winner_spreader meets an agent 𝑏 with ⟨𝑖 ′ | 𝑗 ′ ⟩ such that [𝑖, 𝑗] 𝑘 ⊊ [𝑖 ′, 𝑗 ′ ] 𝑘 , set 𝑏 to winner_spreader and 𝑎 to winner if 𝑖 = 𝑖 ′ and to loser otherwise. (6) token simplification: If an agent 𝑎 with ⟨𝑖 | 𝑗⟩ at winner_spreader meets an agent 𝑏 at winner_spreader with ⟨𝑖 ′ | 𝑗 ′ ⟩ such that [𝑖, 𝑗] 𝑘 ⊆ [𝑖 ′, 𝑗 ′ ] 𝑘 , set 𝑎 to winner if 𝑖 = 𝑖 ′ and to loser otherwise. (7) information spreading: If an agent 𝑎 with ⟨𝑖 | 𝑗⟩ at winner_spreader meets an agent 𝑏 with ⟨𝑖 | 𝑗 ′ ⟩, set 𝑏 to winner. If 𝑏 is of the form ⟨𝑖 ′ | 𝑗 ′ ⟩ with 𝑖 ′ ≠ 𝑖, and [𝑖 ′, 𝑗 ′ ] 𝑘 ⊊ [𝑖, 𝑗] 𝑘 , set 𝑏 to loser. In parallel, the out value of agents is also updated: (i) If an agent 𝑎 with ⟨𝑖 |𝑖⟩ meets an agent 𝑏 of the form ⟨𝑖 ′ | 𝑗 ′ ⟩ with 𝑖 ′ ≠ 𝑗 ′ , set out𝑏 to 𝑖.
Ranking Opinions with Few States in Population Protocols
(ii) If an agent 𝑎 with ⟨𝑖 | 𝑗⟩ at winner_spreader meets an agent 𝑏 of the form ⟨𝑖 ′ | 𝑗 ′ ⟩ with [𝑖 ′, 𝑗 ′ ] 𝑘 ⊆ [𝑖, 𝑗] 𝑘 , set out𝑏 to 𝑖. We say that an agent has a token if it is at winner_spreader, and doesn’t have a token if it it is at either winner or loser. Theorem 4.2 (★). Let 𝑀 = 𝜇0, 𝜇1, . . . 𝜇𝑟 −1 be the colors in relative majority. In the Circles_TieSharing protocol, eventually all agents with initial color in 𝑀 are at winner_spreader or winner while all other agents are at loser. Moreover, the output of every winner or winner_spreader is its initial color, while the output of loser agents is one of the winning colors. The protocol uses 3𝑘 3 many states. This can be dropped to 3𝑘 2 if we only require each agent to only output whether their color win or lose.
4.3
Breaking ties
Instead of reporting or sharing ties it is also possible to break them, meaning in case of a tie all agents agree on one of the colors in relative majority. We adapt Circles by adding a single bit 𝑡𝑖𝑒_𝑏𝑟𝑒𝑎𝑘_𝑡𝑜𝑘𝑒𝑛 (short 𝑡𝑏𝑡) and by running additional steps in parallel to Circles. We call the resulting protocol Circles_TieBreak. We say that an agent 𝑎 carries the tie-break token if 𝑡𝑏𝑡𝑎 = 1, while agents with 𝑡𝑏𝑡 = 0 do not. The idea is as follows: whenever two agents exchange their kets, a tie-breaking token is generated. When two tokens meet, one token is destroyed. The token is always passed along to the braket with the largest weight. The idea we rely on is that in case of a tie the braket with largest weight is formed of the bra and the ket of two majority colors. In case there is no tie, as before an agent with ⟨𝑖 |𝑖⟩ for the unique majority color 𝑖 ∈ [0, 𝑘 −1] exists, obtaining the maximum weight of 𝑘. More precisely the Circles_TieBreak protocol is obtained from the Circles protocol by executing the following steps in sequence after applying the transition function of Circles. Note that agents may apply multiple steps (e.g. (2) and (3)) in a single interaction. (1) token generation: If the agents exchange their kets (due to Circles) and neither one currently holds a tie-break token, then one of them generates a token (sets 𝑡𝑏𝑡 from 0 to 1). (2) token destruction: If both agents hold a tie-break token, then one of them destroys its token (sets 𝑡𝑏𝑡 from 1 to 0). (3) token transfer: If exactly one agent holds a tie-break token, then they pass the token to the one with the larger weight. In case the weight of the agents is identical, then they pass the token to the one with the larger bra (to pass a token from 𝑎 to 𝑏, set 𝑡𝑏𝑡𝑎 from 0 or 1 to 0 and 𝑡𝑏𝑡𝑏 from 0 or 1 to 1). After applying the rules above, the output of agents is set: • If agent 𝑎 has the token, set out 𝑎 =out𝑏 = 𝑖𝑎 , where 𝑎 has braket ⟨𝑖𝑎 | 𝑗𝑎 ⟩. In case we do not specify which of the agents should generate or destroy a token, it does not matter for the correctness of the protocol, so w.l.o.g. we chose the initiator. Theorem 4.3 (★). Circles_TieBreak solves the relative majority problem against a weakly-fair scheduler. If there is a tie, agents all output the same color, one of the majority ones. It requires 2𝑘 3 many states, which can be reduced to 3𝑘 2 if agents are not required to output the majority color, but only whether their color wins or loses.
PODC ’26, July 6–10, 2026, Egham, United Kingdom
5
Unordered setting
The Circles protocol, which we introduce in this work to solve relative majority, relies on numerical representations of the colors in order to compute a distance between them. In this section we describe how to adapt Circles to the unordered setting, in which agents are only able to compare colors for equality and to memorize them. We use the overall idea proposed by Natale and Ramezani [26] which is to combine our protocol with an ordering protocol that assigns to all agents of some initial color from color set 𝐶 the same numeric label from label set 𝐾 = [𝑘 − 1]. We, however, use another ordering protocol, that is more memory-efficient.
5.1
The Ordering protocol
The protocol reuses some ideas proposed by Natale and Ramezani [26] and combines them with a modified version of the protocol proposed by Cai et al. [16], solving (a variant of) the leader election problem. Initially all agents receive label 0. Ordering elects one leader per color among the agents initially supporting that color (by using the asymmetry of interactions). Whenever two leaders with different colors meet (recall that the agents can check for equality between colors), then one of them increments its label by one modulo 𝑘 in case they have the same label. Non-leaders simply copy the label of their leader. Eventually there is a unique leader per color and all leaders store a different label, that they then distribute to the non-leaders. Theorem 5.1 (★). Ordering solves the ordering problem with 𝑂 (𝑘 2 ) states. Intuitively the proof of correctness associates a potential function with every configuration that measures how far away the configuration is from containing a valid ordering. It decreases by a lot in case a leader chooses a previously unused label and by a little in case a leader gets closer to an unused label, until it eventually reaches 0 and an ordering is established.
5.2
The Ord-Circles protocol
The output of Ordering is used as input to Circles. To reiterate: Ordering computes a numeric label from set 𝐾 = [𝑘 − 1] for an agents initial color from (the arbitrary) set 𝐶. That label is stored as the agents bra, which functions as input to Circles. One important property that is required for the correctness of Circles is that it maintains the invariant from Lemma 3.3, so for every bra ⟨𝑖 | in the population for some 𝑖 ∈ 𝐾, there needs to be a matching ket |𝑖⟩ in the population as well. Care must therefore be taken when overwriting the bra of an agent with a new label. Whenever Ordering wants to update an agents bra, we therefore make sure that it is done in a way that maintains the invariant. We say that an agent is consistent in case its braket is ⟨𝑖 |𝑖⟩ for 𝑖 ∈ 𝐾 and inconsistent otherwise. Before applying changes to an agent’s bra, we first wait for the agent to become consistent. Then its braket can be re-initialized to a new value ⟨𝑗 | 𝑗⟩ and Invariant 3.3 still holds. The idea of waiting for agents to become consistent before transmitting changes of the ordering protocol to the relative majority protocol also originates from Natale and Ramezani [26].
PODC ’26, July 6–10, 2026, Egham, United Kingdom
In order to remember what changes Ordering wants to apply to the bra of an agent until that agent becomes consistent, we introduce an ordering state. The ordering state stores whether Ordering wants to increment the bra, copy it from the leader or leave it unchanged. For that it can take one of the values 𝐼 , 𝐶𝐿, 𝐶𝐿𝑊 or 𝑈 (for increment, copy leader, copy leader wait or unchanged). The two separate states 𝐶𝐿 and 𝐶𝐿𝑊 are required to make the following distinction: an agent in ordering state 𝐶𝐿𝑊 wants to copy the label of its leader, but first has to wait to become consistent, while an agent in ordering state 𝐶𝐿 is already consistent and now only has to wait to meet its leader in order to copy its label. Agents in ordering state 𝑈 will be called stable, because they do not want to make any changes to their bra. Agents in 𝐼 or 𝐶𝐿𝑊 will be called unstable to indicate they want to change their bra, but first need to become consistent. Finally agents in 𝐶𝐿 we call pending, highlighting that they are already consistent and only waiting to meet their leader. Formally the Ord-Circles protocol which solves relative majority in the unordered setting works as follows. Memory organization and initialization: Agents store all memory entries related to Circles: ⟨𝑖 | 𝑗⟩, 𝑜𝑢𝑡 and depending on the use case bits to break, share or report ties. Additionally there are memory entries 𝑖𝑐 to store the initial color of an agent (in some representation) and the leader bit 𝑙𝑑 required for Ordering. Agents also store an ordering state 𝑜𝑠 ∈ {𝑈 , 𝐼, 𝐶𝐿, 𝐶𝐿𝑊 }. Initially 𝑖 = 𝑗 = 0, 𝑜𝑠 = 𝑈 and 𝑙𝑑 = 1. Both 𝑖𝑐 and 𝑜𝑢𝑡 are initialized with the input color of the agent. Transition function: When we say an agent with braket ⟨𝑖 |𝑖⟩ re-initializes for some value 𝑖 ′ , then it sets its braket to ⟨𝑖 ′ |𝑖 ′ ⟩, 𝑜𝑠 = 𝑈 , 𝑜𝑢𝑡 = 𝑖𝑐 and re-initializes all variables related to reporting or breaking ties as described in the respective sections. An interaction between agents 𝑎 and 𝑏, with brakets ⟨𝑖𝑎 | 𝑗𝑎 ⟩ and ⟨𝑖𝑏 | 𝑗𝑏 ⟩, results in state updates by performing the following steps in sequence: (1) In case 𝑎 and 𝑏 are leaders of the same color, then 𝑎 stops being a leader, meaning it sets 𝑙𝑑𝑎 = 0. In case 𝑏 is the leader of 𝑎, 𝑖𝑎 ≠ 𝑖𝑏 and 𝑎 is not pending, then 𝑎 sets 𝑜𝑠𝑎 = 𝐶𝐿𝑊 . In case 𝑎 and 𝑏 are leaders of different colors, have the same bra and 𝑏 is stable, then 𝑎 sets 𝑜𝑠𝑎 = 𝐼 . This step corresponds to Ordering. (2) If 𝑎 is pending, 𝑎 and 𝑏 have the same initial color 𝑖𝑐 ∈ 𝐶 and 𝑏 is a leader, then 𝑎 re-initializes its label with value 𝑖𝑏 . Pending agents do otherwise not interact in any of the other steps. (3) If 𝑎 is unstable and inconsistent, and 𝑗𝑏 = 𝑖𝑎 , then 𝑎 and 𝑏 exchange their 𝑘𝑒𝑡, making 𝑎 consistent. (4) If 𝑎 is unstable and consistent, then in case 𝑜𝑠𝑎 = 𝐼 , 𝑎 reinitializes for the value (𝑖𝑎 + 1) mod 𝑘. In case 𝑜𝑠𝑎 = 𝐶𝐿𝑊 , then 𝑎 sets 𝑜𝑠𝑎 = 𝐶𝐿. (5) 𝑎 and 𝑏 interact according to Circles. In order for agents to output elements from the set of colors 𝐶 instead of elements from the set of labels 𝐾, manipulate Circles as follows: Whenever some agent 𝑎 sets 𝑜𝑢𝑡𝑎 = ⟨𝑖𝑏 | for some agent 𝑏 (potentially 𝑎 = 𝑏), instead set 𝑜𝑢𝑡𝑎 = 𝑖𝑐𝑏 . Theorem 5.2 (★). Ord-Circles solves relative majority in the unordered setting against a weakly-fair scheduler using 𝑂 (𝑘 4 ) states.
Breitkopf, Dallot, El-Hayek and Schmid
This can be reduced to 𝑂 (𝑘 3 ) many states if every agent is only required to report whether their color wins or loses. The proof of correctness essentially argues that eventually an ordering among the colors is established and that afterwards Circles runs on a population correctly representing the initial color distribution with the bra and ket of agents.
6
The Ranking protocol
In this section we discuss how to adapt the Circles protocol to solve the ranking problem under a globally faire scheduler. For the rest of this section, we denote by 𝑥𝑖 , for each 𝑖 ∈ [0, 𝑘 −1], the number of agents with color 𝑖 in the input. Definition 6.1. In the ranking problem, each agent is given as an input a color in [0, 𝑘 − 1]. We assume that no two colors have the same number of agents initially, and that all colors are represented at least once. At the end of the protocol, each agent with input 𝑖 should output a value 𝑗 ∈ [0, 𝑘 − 1], such that |{ℓ ∈ [0, 𝑘 − 1] : 𝑥 ℓ > 𝑥𝑖 }| = 𝑗, which corresponds to the ranking of the color in the input, that is, the majority color outputs 0, the second most popular color outputs 1, and so on. Theorem 1.2. There is a protocol that solves the ranking problem in case of a globally fair scheduler, and uses 2 · 𝑘 4 many states. Remark 1. This algorithm can be easily modified to work for the case where the colors are unordered, with the same number of states. Let us first discuss the intuition and observations that lead us to such a protocol. First, in the Circles protocol, we notice that, in the very specific case where color 0 is the most popular one, followed by 1, then 2, and so on until 𝑘 − 1, then the structure of the configuration at stabilization is very straightforward: each set of the Greedy Independent Sets is of the form [0, 𝑖] for 𝑖 ∈ [0, 𝑘−1]. In turn, this means that all of the brakets are of the form ⟨𝑖 |𝑖 + 1 mod 𝑘⟩ or ⟨𝑖 |0⟩ for 𝑖 ∈ [0, 𝑘 − 1]. In fact, we can show that this is a if and only if situation: Lemma 6.2. In the Circles protocol, the input is such that 𝑥 0 > 𝑥 1 > · · · > 𝑥𝑘 −1 if and only if, after stabilization, all of the brakets are of the form ⟨𝑖 |𝑖 + 1 mod 𝑘⟩ or ⟨𝑖 |0⟩ for 𝑖 ∈ [0, 𝑘 − 1]. Proof of Lemma 6.2. The forwards implication is straightforward, as discussed above. For the backwards implication, note that if the ket | 𝑗⟩ is only present in brakets ⟨𝑗 − 1 mod 𝑘 | 𝑗⟩, then there are at least as many agents with bra ⟨𝑗 − 1 mod 𝑘 | as agents with bra ⟨𝑗 |. Therefore 𝑥 𝑗 −1 > 𝑥 𝑗 for all 𝑗 ∈ [1, 𝑘 − 1], and the result holds. □ Thus the idea is to recycle the Circles protocol to be in the situation where the input is the initial order of the colors. For that, we now introduce a 𝑂 (𝑘 4 ) protocol where the bra and ket consist now of 2 different values: ⟨𝑖, 𝔦| and |𝔦, 𝑖⟩ for every 𝑖 ∈ [0, 𝑘 − 1]. 𝔦 ∈ [0, 𝑘 − 1] represents the (belief of) ranking of the color 𝑖. Now, when applying the Circles protocol, the idea is that instead of computing the weights according to the colors value, we compute them according to the rankings’ value. Formally, for every 𝑖, 𝑗 ∈ [0, 𝑘 − 1]
Ranking Opinions with Few States in Population Protocols
( 𝑘 𝑤 (⟨𝑖, 𝔦|𝔧, 𝑗⟩) = (𝔧 − 𝔦) mod 𝑘
if 𝔦 = 𝔧 otherwise
PODC ’26, July 6–10, 2026, Egham, United Kingdom
(1)
It remains to discuss how the value 𝔦 is assigned. We start by assigning 𝔦 ← 𝑖. Moreover, every agent is assigned a token which makes it a leader for its color, that is, this agent is in charge of assigning the ranking of the color to the corresponding color, and broadcast any changes that it decides. When two tokens for the same color meet, one of them has to be deleted. When two tokens for different colors 𝑖 < 𝑗 but same ranking 𝔦 = 𝔧 meet, one of them increases its ranking by one 𝔧 ← 𝔧 + 1. Eventually this ensures that there is a unique leader for each color, and all the rankings are different. Finally, rules should be implemented to ensure that whenever the ranking assigned is not correct, agents are able to change their rankings. We note that if the rankings are not correct, but are unique, and the Circles protocol has stabilized, then there exists two agents of the form ⟨𝑖, 𝔦|𝔧, 𝑗⟩ and ⟨𝑖, 𝔦|𝔩, ℓ⟩ with 𝔧 ≠ 𝔩 and 𝔧, 𝔩 ≠ 0, or there must exist an agent ⟨𝑖, 𝔦|𝔦, 𝑖⟩ with 𝔦 ≠ 0. We now give the lemma that hints at how agents can determine that the current ranking is wrong. Lemma 6.3. In the Circles protocol, after stabilization, if the initial colors do not satisfy 𝑥 0 > 𝑥 1 > · · · > 𝑥𝑘 −1 , and 𝑥𝑖 ≠ 0 ∀𝑖, then either: (1) There exist an agent ⟨𝑖 |𝑖⟩ with 𝑖 ≠ 0, or (2) there exist two agents of the form ⟨𝑖 | 𝑗⟩ and ⟨𝑖 |ℓ⟩ with 𝑗 ≠ ℓ and 𝑗, ℓ ≠ 0. Proof. Assume all agents of the form ⟨𝑖 |𝑖⟩ satisfy 𝑖 = 0, that is, 0 is the majority color. And assume that there exists a 𝑗 such that 𝑥 𝑗 < 𝑥 𝑗+1 , and let ℓ be the smallest such 𝑗. In particular, ℓ ≠ 0 and 𝑥 ℓ −1 > 𝑥 ℓ . Therefore, all of the kets |ℓ⟩ are in agents of the form ⟨ℓ − 1|ℓ⟩, and at least one of such agents exists since 𝑥 ℓ ≠ 0. Moreover, the first greedy independent set that does not contain ℓ contains both ℓ − 1 and ℓ + 1. Therefore there exists an agent of the □ form ⟨ℓ − 1|ℓ + 1⟩. In our case, this means that whenever two agents of the form ⟨𝑖, 𝔦|𝔧, 𝑗⟩ and ⟨𝑖, 𝔦|𝔩, ℓ⟩ with 𝔧 ≠ 𝔩 and 𝔧, 𝔩 ≠ 0 meet, they need to exchange 𝔧 and 𝔩. This can only be allowed if they respectively hold the tokens for 𝑗 and ℓ. Moreover, ⟨𝑖, 𝔦|𝔦, 𝑖⟩ must be able to claim the ranking 𝔦 = 0. We therefore enforce the token of color 𝑗 to be attached to a ket |𝔧, 𝑗⟩. The token should seek the agent ⟨𝑖, 𝔦|𝔧, 𝑗⟩ with minimal 𝔦 to stick to, that is, whenever ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ∗ meets ⟨ℓ, 𝔩|𝔧, 𝑗⟩ (where the asterisk denotes the token on the color of the ket), the token should be transferred to ⟨ℓ, 𝔩|𝔧, 𝑗⟩ only if 𝔩 < 𝔦. We can then enforce that whenever ⟨𝑖, 𝔦|𝔦, 𝑖⟩ ∗ meets ⟨𝑗, 𝔧|0, ℓ⟩ ∗ , they exchange their rankings, that is 𝔩 ← 𝔦, 𝔦 ← 0; and when ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ∗ and ⟨𝑖, 𝔦|𝔩, ℓ⟩ ∗ meet, they also exchange their rankings, that is 𝔧, 𝔩 ← 𝔩, 𝔧. With all of these rules, we are done describing the protocol, and it remains to show that it is correct against a globally fair scheduler. For that, we show below that there is only one configuration that is stable, namely the one where all the assigned rankings of the colors is correct, and where the Circles protocol is stabilized. We then show that this configuration is reachable from all other valid
configurations (that is, configurations reachable from the initial configuration), and this is enough to conclude. Before that, let us describe more formally the protocol. In this description, whenever two agents meet, if multiple cases apply, select only one case: the first case that does not leave the agents unchanged. The ◦ symbol denotes the fact that the existence or not of a token is not important: (1) Initialization: • Each agent in color 𝑖 starts in the state ⟨𝑖, 𝔦 = 𝑖 |𝔦 = 𝑖, 𝑖⟩ ∗ (2) Token deletion: • If ⟨𝑗, 𝔧|𝔦, 𝑖⟩ ∗ meets ⟨ℓ, 𝔩|𝔦 ′, 𝑖⟩ ∗ , with 𝔧 ≤ 𝔩, then ⟨ℓ, 𝔩|𝔦 ′, 𝑖⟩ ∗ becomes ⟨ℓ, 𝔩|𝔦, 𝑖⟩ (3) Ranking uniqueness: • If ⟨𝑗, 𝔧|𝔦, 𝑖⟩ ∗ meets ⟨ℓ, 𝔩|𝔲, 𝑢⟩ ∗ , with 𝔦 = 𝔲 and 𝑖 < 𝑢, then ⟨ℓ, 𝔩|𝔲, 𝑢⟩ ∗ becomes ⟨ℓ, 𝔩|𝔲 + 1, 𝑢⟩ ∗ (in other words, 𝔲 ← 𝔲 + 1). (4) Ranking broadcast: • If ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ∗ meets ⟨𝑢, 𝔲|𝔧′, 𝑗⟩, then ⟨𝑢, 𝔲|𝔧′, 𝑗⟩ becomes ⟨𝑢, 𝔲|𝔧, 𝑗⟩. • If ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ∗ meets ⟨𝑗, 𝔧′ |𝔲, 𝑢⟩ ◦ , then ⟨𝑗, 𝔧′ |𝔲, 𝑢⟩ ◦ becomes ⟨𝑗, 𝔧|𝔲, 𝑢⟩ ◦ (5) Circles: • Recall the weight function from Equation (1). ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ◦ ⟨𝑢, 𝔲|𝔳, 𝑣⟩ ◦ • If agent meets with min{𝑤 (⟨𝑖, 𝔦|𝔳, 𝑣⟩), 𝑤 (⟨𝑢, 𝔲|𝔧, 𝑗⟩)} < min{𝑤 (⟨𝑖, 𝔦|𝔧, 𝑗⟩), 𝑤 (⟨𝑢, 𝔲|𝔳, 𝑣⟩)}, then ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ◦ becomes ⟨𝑖, 𝔦|𝔳, 𝑣⟩ ◦ and ⟨𝑢, 𝔲|𝔳, 𝑣⟩ ◦ becomes ⟨𝑢, 𝔲|𝔧, 𝑗⟩ ◦ (If there are any tokens, they are exchanged to stay with their respective kets). (6) Token transfer: • If ⟨𝑖, 𝔦|𝔦, 𝑖⟩ meets ⟨ℓ, 𝔩|𝔦, 𝑖⟩ ∗ , then ⟨ℓ, 𝔩|𝔦, 𝑖⟩ ∗ becomes ⟨ℓ, 𝔩|𝔦, 𝑖⟩ and ⟨𝑖, 𝔦|𝔦, 𝑖⟩ becomes ⟨𝑖, 𝔦|𝔦, 𝑖⟩ ∗ • If ⟨𝑗, 𝔧|𝔦, 𝑖⟩ meets ⟨ℓ, 𝔩|𝔦, 𝑖⟩ ∗ , with 𝑗 ≠ 𝑖, ℓ ≠ 𝑖 and 𝔧 < 𝔩, then ⟨ℓ, 𝔩|𝔦, 𝑖⟩ ∗ becomes ⟨ℓ, 𝔩|𝔦, 𝑖⟩ and ⟨𝑗, 𝔧|𝔦, 𝑖⟩ becomes ⟨𝑗, 𝔧|𝔦, 𝑖⟩ ∗ (7) Ranking swap: • If ⟨𝑖, 𝔦|𝔦, 𝑖⟩ ∗ meets ⟨𝑢, 𝔲|0, 𝑣⟩ ∗ with 𝑣 ≠ 𝑖, 𝔦 ≠ 0, then ⟨𝑖, 𝔦|𝔦, 𝑖⟩ ∗ becomes ⟨𝑖, 0|0, 𝑖⟩ ∗ and ⟨𝑢, 𝔲|0, 𝑣⟩ ∗ becomes ⟨𝑢, 𝔲|𝔦, 𝑣⟩ ∗ • If ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ∗ meets ⟨𝑖, 𝔦|𝔩, ℓ⟩ ∗ with 𝑗, ℓ ≠ 𝑖, then ⟨𝑖, 𝔦|𝔧, 𝑗⟩ ∗ becomes ⟨𝑖, 𝔦|𝔩, 𝑗⟩ ∗ and ⟨𝑖, 𝔦|𝔩, ℓ⟩ ∗ becomes ⟨𝑖, 𝔦|𝔧, ℓ⟩ ∗ . (8) Output: • An agent in state ⟨𝑖, 𝔦|𝔧, 𝑗⟩ outputs 𝔦. We now define the configuration that we show below is stable: Definition 6.4. Let 𝑋 be the following configuration: (1) There exists exactly 𝑘 tokens, one for each 𝑖 ∈ [0, 𝑘 − 1]. Each token is on a ket of different color. (2) The tokens are associated to 𝑘 different rankings, defined by: 𝑖 ∈ [0, 𝑘 − 1], r(𝑖) := |{ℓ ∈ [0, 𝑘 − 1] : 𝑥 ℓ > 𝑥𝑖 }|. (3) Every bra and ket are of the form ⟨𝑖, r(𝑖)| for 𝑖 ∈ [0, 𝑘 − 1] or |r( 𝑗), 𝑗⟩ for 𝑗 ∈ [0, 𝑘 − 1] (4) The Circles protocol is stabilized, that is, all kets are of the form either ⟨𝑖, r(𝑖)|r( 𝑗) = r(𝑖) + 1, 𝑗⟩ ◦ or ⟨𝑖, r(𝑖)|r( 𝑗) = 0, 𝑗⟩ ◦ (5) All tokens are on brakets of the form ⟨𝑖, r(𝑖) = 0|r(𝑖) = 0, 𝑖⟩ ∗ or ⟨𝑖, r(𝑖)|r( 𝑗) = r(𝑖) + 1, 𝑗⟩ ∗ . Lemma 6.5 (★). 𝑋 is a stable configuration.
PODC ’26, July 6–10, 2026, Egham, United Kingdom
Breitkopf, Dallot, El-Hayek and Schmid
We finally show that 𝑋 is reachable from every configuration.
(3) The rankings of all bras and kets are consistent with the rankings assigned by the tokens. (4) The Circles protocol is stabilized on this particular ranking, that is, Rule (5) cannot modify anymore any pair of agents.
Proposition 6.6. 𝑋 is reachable from any valid configuration. The rest of this section is dedicated to proving this proposition. We do so by taking any valid configuration, and giving a series of intermediate configurations, each reachable from the previous configuration, until we reach 𝑋 . Let 𝐴 be any valid configuration. Lemma 6.7. 𝐴 satisfies the following conditions: (1) for every 𝑖, there exists exactly 𝑥𝑖 many bras and 𝑥𝑖 many kets of the form ⟨𝑖, ·| and |·, 𝑖⟩ respectively. (2) for every 𝑖, there exist at least one ket of the form |·, 𝑖⟩ ∗ Proof. Both statement are straightforward, as the first and second elements of the bras and ket respectively are never changed, only exchanged, and as the token is passed around in a leader election fashion over the kets of the form |·, 𝑖⟩. □
Proof. From configuration 𝐷, Rules (2) to (4) cannot modify any agent anymore. Since the Circles protocol works against a weakly fair scheduler, there exists a sequence of interactions that lead to its stabilization. Following this sequence, by skipping any interaction that wouldn’t modify any agents, we reach 𝐸 −1 . □ Lemma 6.12 (★). For every ℓ ∈ [0, 𝑘 − 1], there exists a configuration 𝐸 ℓ reachable from 𝐸 ℓ −1 with the following conditions: (1) for every 𝑖, there exists exactly 𝑥𝑖 many bras and 𝑥𝑖 many kets of the form ⟨𝑖, ·| and |·, 𝑖⟩ respectively. (2) for every 𝑖, there exist exactly one ket of the form |·, 𝑖⟩ ∗ . Moreover, the pairs formed by these kets form a bijection of [0, 𝑘 −1] to [0, 𝑘 −1], that is to say, the rankings of the tokens are unique. (3) The rankings of all bras and kets are consistent with the rankings assigned by the tokens. (4) The Circles protocol is stabilized on this particular ranking, that is, Rule (5) cannot modify anymore any pair of agents. (5) 𝐸 ℓ contains the kets |r( 𝑗), 𝑗⟩ ∗ for all 𝑖 ≤ ℓ, that is, all rankings up to ℓ are correct.
Lemma 6.8. There exists a configuration 𝐵 reachable from 𝐴 with the following conditions: (1) for every 𝑖, there exists exactly 𝑥𝑖 many bras and 𝑥𝑖 many kets of the form ⟨𝑖, ·| and |·, 𝑖⟩ respectively. (2) for every 𝑖, there exist exactly one ket of the form |·, 𝑖⟩ ∗ . Proof. Again, this is straightforward using Rules (2) and (3), and the fact that the second elements of kets are only exchanged. □ Lemma 6.9. There exists a configuration 𝐶 reachable from 𝐵 with the following conditions: (1) for every 𝑖, there exists exactly 𝑥𝑖 many bras and 𝑥𝑖 many kets of the form ⟨𝑖, ·| and |·, 𝑖⟩ respectively. (2) for every 𝑖, there exist exactly one ket of the form |·, 𝑖⟩ ∗ . Moreover, the pairs formed by these kets form a bijection of [0, 𝑘 −1] to [0, 𝑘 −1], that is to say, the rankings of the tokens are unique. Proof. From configuration 𝐵, we can select the pairs of agents to interact that only use Rule (3) to get the desired configuration. □ Lemma 6.10. There exists a configuration 𝐷 reachable from 𝐶 with the following conditions: (1) for every 𝑖, there exists exactly 𝑥𝑖 many bras and 𝑥𝑖 many kets of the form ⟨𝑖, ·| and |·, 𝑖⟩ respectively. (2) for every 𝑖, there exist exactly one ket of the form |·, 𝑖⟩ ∗ . Moreover, the pairs formed by these kets form a bijection of [0, 𝑘 −1] to [0, 𝑘 −1], that is to say, the rankings of the tokens are unique. (3) The rankings of all bras and kets are consistent with the rankings assigned by the tokens. Proof. From configuration 𝐶, rules (2) and (3) do not change any agent anymore. Therefore, from 𝐶, it suffices for each agent with a token to meet the agents with the corresponding bra or ket to assign them the correct ranking. □ Lemma 6.11. There exists a configuration 𝐸 −1 reachable from 𝐷 with the following conditions: (1) for every 𝑖, there exists exactly 𝑥𝑖 many bras and 𝑥𝑖 many kets of the form ⟨𝑖, ·| and |·, 𝑖⟩ respectively. (2) for every 𝑖, there exist exactly one ket of the form |·, 𝑖⟩ ∗ . Moreover, the pairs formed by these kets form a bijection of [0, 𝑘 −1] to [0, 𝑘 −1], that is to say, the rankings of the tokens are unique.
As 𝐸𝑘 −1 = 𝑋 , this concludes the proof of Proposition 6.6. Proof of Theorem 1.2. Since 𝑋 is a stable configuration, by Lemma 6.5, and is reachable from any other configuration by Proposition 6.6, we know that 𝑋 is the only stable configuration, and is always reached under a globally fair scheduler. □
7
Future work
Our protocol solves relative majority always-correctly with 𝑂 (𝑘 3 ) states, narrowing the gap with the Ω(𝑘 2 ) lower bound. Its versatility further allows computing the full ranking, making it a promising building block for more complex distributed tasks. During our work, both Circles and an independent protocol based on a different logic hit Ω(𝑘 3 ) states as a hard barrier. We therefore believe the most fruitful direction is strengthening the Ω(𝑘 2 ) lower bound. Such improvements are rare in the population protocol model, and we hope this work motivates the development of new lower bound techniques with broader impact on population protocols.
Acknowledgments Funded by the European union. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/I5982. For open access purposes, the author has applied a CC BY public copyright license to any author-accepted manuscript version arising from this submission.
Ranking Opinions with Few States in Population Protocols
References [1] Dan Alistarh, James Aspnes, David Eisenstat, Rati Gelashvili, and Ronald L. Rivest. 2017. Time-Space Trade-offs in Population Protocols. In Proceedings 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 [2] Dan Alistarh, James Aspnes, and Rati Gelashvili. 2018. Space-Optimal Majority in Population Protocols. In Proceedings 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 [3] Dan Alistarh, Krishnendu Chatterjee, Mehrdad Karrabi, and John Lazarsfeld. 2024. Game Dynamics and Equilibrium Computation in the Population Protocol Model. In Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing (PODC 2024). ACM, New York, NY, USA, 40–49. doi:10.1145/3662158.3662768 [4] Dan Alistarh and Rati Gelashvili. 2018. Recent Algorithmic Advances in Population Protocols. ACM SIGACT News 49, 3 (2018), 63–73. doi:10.1145/3289137. 3289150 [5] Dan Alistarh, Rati Gelashvili, and Milan Vojnović. 2015. Fast and Exact Majority in Population Protocols. In Proceedings 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 [6] 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. In Proceedings of the 2023 ACM Symposium on Principles of Distributed Computing (PODC 2023). ACM, Orlando, FL, USA, 13–23. doi:10.1145/3583668.3594589 [7] Dana Angluin, James Aspnes, Zoë Diamadi, Michael J. Fischer, and René Peralta. 2006. Computation in networks of passively mobile finite-state sensors. Distributed computing 18, 4 (2006), 235–253. doi:10.1145/1011767.1011810 [8] James Aspnes, Joffroy Beauquier, Janna Burman, and Devan Sohier. 2016. Time and Space Optimal Counting in Population Protocols. In Proceedings 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 [9] 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. In Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, (SODA 2022). SIAM, Alexandria, VA, USA, 3417–3429. doi:10.1137/1.9781611977073.135 [10] 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. In Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing (PODC 2022). ACM, Salerno, Italy, 224–234. doi:10.1145/ 3519270.3538447 [11] Luca Becchetti, Andrea E. F. Clementi, Emanuele Natale, Francesco Pasquale, and Riccardo Silvestri. 2015. Plurality consensus in the gossip model. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015). ACM, San Diego, USA, 371–390. doi:10.1137/1.9781611973730.27 [12] 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/S00446020-00385-0 [13] Petra Berenbrink, Tom Friedetzky, George Giakkoupis, and Peter Kling. 2016. Efficient Plurality Consensus, Or: the Benefits of Cleaning up from Time to Time. In Proceedings 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 [14] Michael Blondin and François Ladouceur. 2023. Population Protocols with Unordered Data. In Proceedings of the 50th International Colloquium on Automata, 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 [15] 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 [16] 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 [17] Luca Cardelli and Attila Csikász-Nagy. 2012. The cell cycle switch computes approximate majority. Scientific reports 2, 1 (2012), 656–656. [18] Philipp Czerner, Javier Esparza, and Jérôme Leroux. 2023. Lower bounds on the state complexity of population protocols. Distributed computing 36, 3 (2023), 209–218. doi:10.1007/S00446-023-00450-4 [19] David Doty. 2014. Timing in chemical reaction networks. In 25th Annual ACMSIAM Symposium on Discrete Algorithms (SODA 2014). Portland (USA), 772–784. doi:10.1137/1.9781611973402.57
PODC ’26, July 6–10, 2026, Egham, United Kingdom
[20] 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. In 62nd IEEE Annual Symposium on Foundations of Computer Science, (FOCS 2021). IEEE, Denver, CO, USA, 1044–1055. doi:10.1109/FOCS52979.2021.00104 [21] Moez Draief and Milan Vojnović. 2012. Convergence Speed of Binary Interval Consensus. SIAM Journal on Control and Optimization 50, 3 (2012), 1087–1109. doi:10.1137/110823018 [22] 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. In Proceedings of the ACM Symposium on Principles of Distributed Computing, (PODC 2025). ACM, Huatulco, Mexico, 532–540. doi:10. 1145/3732772.3733505 [23] Robert Elsässer and Tomasz Radzik. 2018. Recent Results in Population Protocols for Exact Majority and Leader Election. In The Distributed Computing Column, Stefan Schmid (Ed.). [24] Leszek Gąsieniec, David Hamilton, Russell Martin, Paul G. Spirakis, and Grzegorz Stachowiak. 2017. Deterministic Population Protocols for Exact Majority and Plurality. In Proceedings 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 [25] 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 [26] Emanuele Natale and Iliad Ramezani. 2019. On the Necessary Memory to Compute the Plurality in Multi-Agent Systems. In Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC 2019). Rome (Italy), 323–338. http://arxiv.org/abs/1901.06549 [27] 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 networks 1, 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 (following the construction process in Definition 3.1), any color whose count is not zero yet is added into 𝐺 𝑝 and its count is decremented by one. The color 𝜇 appears in the population strictly more than any other, it therefore holds that ∀𝑝 ∈ [1, 𝑞], 𝜇 ∈ 𝐺 𝑝 . Let now 𝑖 ∈ [0, 𝑘 − 1] be a color contained in a set 𝐺 𝑝 for some 𝑝 ∈ [1, 𝑞]. It holds that ∀𝑙 ≤ 𝑝, 𝑖 ∈ 𝐺𝑙 as because color 𝑖 is available to populated 𝐺 𝑝 , it was also available when 𝐺𝑙 was filled earlier. It is therefore not possible that a color 𝑗 ≠ 𝜇 is contained in 𝐺𝑞 as 𝑗 would be contained in all sets and thus 𝑗 would also be in relative majority, contradicting 𝜇 being the unique color in relative majority. □
8.2
Proof of Lemma 3.3
Proof. Every agent is initialized with braket ⟨𝑖 |𝑖⟩ for some 𝑖 ∈ [0, 𝑘 − 1] and the claim initially holds. Agents subsequently only ever update their braket, by exchanging kets among each other. The overall number of bras and kets in the population therefore does not change during a computation. □
8.3
Proof of Theorem 4.1
Theorem 4.1 (★). Circles_TieReport solves the relative majority problem, where all agents output the color of the majority if the majority is strict. If there is a tie, agents do not output a color, but rather report that there is a tie. It requires 3𝑘 3 many states, which can be reduced to 4𝑘 2 if agents are not required to output the majority color, but only whether their color wins or loses. The result follows from Theorem 3.5 together with the following lemma.
PODC ’26, July 6–10, 2026, Egham, United Kingdom
Lemma 8.1. If there is no tie in the input colors then all agents eventually are at no_tie. If there is a tie in the input colors then all agents eventually are at tie or tie_spreader. Proof. We first assume that there is no tie. The only rules that sets an agent to tie_spreader is the first rule; this rule eventually stops triggering since all agents stop exchanging their ket past a certain time (Theorem 3.4). As there is no tie, there will be a remaining agent in state ⟨𝜇|𝜇⟩ past a certain time and that agent eventually sets all other agents to no_tie. We now assume that there is a tie. Past a certain time, no agent will be in state ⟨𝑖 |𝑖⟩ for any 𝑖. There hence exists an interaction where the last agent of the form ⟨𝑖 |𝑖⟩ decays into ⟨𝑖 | 𝑗⟩ with 𝑖 ≠ 𝑗. When this happens that agent ⟨𝑖 | 𝑗⟩ is at tie_spreader and will set all other agents at no_tie to tie. □
8.4
Proof of Theorem 4.2
Theorem 4.2 (★). Let 𝑀 = 𝜇0, 𝜇1, . . . 𝜇𝑟 −1 be the colors in relative majority. In the Circles_TieSharing protocol, eventually all agents with initial color in 𝑀 are at winner_spreader or winner while all other agents are at loser. Moreover, the output of every winner or winner_spreader is its initial color, while the output of loser agents is one of the winning colors. The protocol uses 3𝑘 3 many states. This can be dropped to 3𝑘 2 if we only require each agent to only output whether their color win or lose. To prove this theorem, we split it into two cases, depending on whether 𝑟 = 1 or 𝑟 > 1. In the rest of this section, we simplify the notation and write 𝜇𝑠 for 𝜇𝑠 mod 𝑟 Lemma 8.2. If 𝑟 = 1, all agents with initial color in 𝑀 are at winner while all other agents are at loser. Proof. Eventually the only agents with brakets ⟨𝑖 |𝑖⟩ are ⟨𝜇 0 |𝜇 0 ⟩, by Lemmas 3.7 and 3.2. Those agents are at winner from either the initial configuration or the token destructor rule. Moreover, those agents will set all agents ⟨𝜇 0 | 𝑗⟩ to winner and all agents ⟨𝑖 | 𝑗⟩ with 𝑖 ≠ 𝜇 0 to loser, by the token destruction rule. The out of all agents is set to 𝜇0 by rule (i). □ The idea for the case 𝑟 > 1 relies heavily on the following observation: Claim 2. After Stabilization (Theorem 3.4), every braket ⟨𝑖 | 𝑗⟩ held by an agent satisfies that there exists an 𝑠 such that [𝑖, 𝑗] 𝑘 ⊆ [𝜇𝑠 , 𝜇𝑠+1 ] 𝑘 . This claim is immediate by the definitions of the Greedy independent sets (Definition 3.1), the corresponding Circle Braket Sets (Definition 3.6) and Lemma 3.7. We thus show below that starting at some point in time, there exists a token in every interval [𝜇𝑠 , 𝜇𝑠+1 ] 𝑘 , there exists an agent ⟨𝜇𝑠 |𝜇𝑠+1 ⟩ that holds a token, and can spread the information for all agents in that interval. We start by proving the following lemma. It relies on our definition of Greedy independent sets (Definition 3.1) and the corresponding Circle Braket Sets (Definition 3.6). Lemma 8.3. Let 𝑟 > 1. Let 𝑇 (𝑡) be the set of agents that have a token after interaction 𝑡 ∈ N. There exists an ℓ ∈ N and a set of agents
Breitkopf, Dallot, El-Hayek and Schmid
𝑇 such that for all 𝑡 ≥ ℓ, 𝑇 (𝑡) = 𝑇 . Moreover, the multiset of brakets of all agents in 𝑇 is equal to 𝑓 (𝐺𝑞 ). Proof. Let 𝑡 be the interaction where the brackets of the agents stop changing (Theorem 3.5). The population contains agents with brakets ⟨𝜇 0 |𝜇 1 ⟩, ⟨𝜇 1 |𝜇 2 ⟩ ,. . . , ⟨𝜇𝑟 −1 |𝜇 0 ⟩, by Lemma 3.7. We show that starting at ℓ, we have the following invariant: Claim 3. For any 𝑡 ′ ≥ ℓ, we have that for any 𝑠 ∈ [1, 𝑟 ], there exists a 𝑣 ∈ [0, 𝑘 − 1] with [𝜇𝑠 , 𝑣] 𝑘 ⊆ [𝜇𝑠 , 𝜇𝑠+1 ] 𝑘 , and such that there exists an agent with braket ⟨𝜇𝑠 |𝑣⟩ either at winner_spreader or loser. Proof. Let us fix an 𝑠 and look at the last point in time 𝜏 where a ⟨𝜇𝑠 | exchanged kets. By token generation, a token is thus created. We then prove the claim by induction. Assume that after interaction 𝜏 ′ ≥ 𝜏, we have that there exists a 𝑣 ∈ [0, 𝑘 − 1] with [𝜇𝑠 , 𝑣] 𝑘 ⊆ [𝜇𝑠 , 𝜇𝑠+1 ] 𝑘 , and such that there exists an agent with braket ⟨𝜇𝑠 |𝑣⟩ either at winner_spreader or loser. We prove this holds as well after interaction 𝜏 ′ + 1. If the interaction did not involve a braket ⟨𝜇𝑠 |𝑣⟩ at either loser or winner_spreader, the induction is immediate. We thus assume that such an agent is involved in the interaction. If the interaction 𝜏 ′ + 1 is either token generation, or token destructor, the results holds trivially, as that same agent is set to either winner_spreader or loser (It cannot be set at winner using token destructor, as that would imply the existence of a ⟨𝜇𝑠 |𝜇𝑠 ⟩, which is incompatible with the fact that 𝑟 > 1 and the definition of 𝜏). If interaction 𝜏 ′ + 1 is a token destruction, agent in ⟨𝜇𝑠 |𝑣⟩ must have been set to loser, as the alternative (being set to winner would mean that ⟨𝜇𝑠 |𝑣⟩ met ⟨𝜇𝑠 |𝜇𝑠 ⟩, a contradiction to 𝜏 being the last point in time where ⟨𝜇𝑠 | exchanged kets, as we know by Lemma 3.7 that ⟨𝜇𝑠 |𝜇𝑠 ⟩ is not in the final braket multiset). This maintains the invariant. If interaction 𝜏 ′ + 1 is a token ascent, then either agent in ⟨𝜇𝑠 |𝑣⟩ must have been set to loser, or the agent it interacted with had a token and was in a state of the form ⟨𝜇𝑠 | 𝑗⟩ for some 𝑗 ∈ [0, 𝑘 − 1]. In that case the invariant holds after 𝜏 ′ + 1, because either ⟨𝜇𝑠 |𝑣⟩ is at loser, or ⟨𝜇𝑠 | 𝑗⟩ being at winner_spreading. If interaction 𝜏 ′ + 1 is a token simplification, then either agent in ⟨𝜇𝑠 |𝑣⟩ must have been set to loser, or the agent it interacted with had a token and was in a state of the form ⟨𝜇𝑠 | 𝑗⟩ for some 𝑗 ∈ [0, 𝑘 − 1]. In that case the invariant holds after 𝜏 ′ + 1, because either ⟨𝜇𝑠 |𝑣⟩ is at loser, or ⟨𝜇𝑠 | 𝑗⟩ being at winner_spreading. If interaction 𝜏 ′ + 1 is an information spreading, either ⟨𝜇𝑠 |𝑣⟩ is set to loser, which maintains the invariant, or it met some braket ⟨𝜇𝑠 | 𝑗⟩ for some 𝑗 ∈ [0, 𝑘 − 1] at winner_spreader. In that case the invariant holds after 𝜏 ′ + 1, not necessarily due to ⟨𝜇𝑠 |𝑣⟩, but rather ⟨𝜇𝑠 | 𝑗⟩ being at winner_spreading. □ At time 𝑡, the population also contains at least one agent at winner_spreader, which was created by the last ket exchange. This token will ascend until it becomes attached to a ⟨𝜇𝑠 |𝜇𝑠+1 ⟩ for some 𝑠 ∈ [0, 𝑘 − 1]. In case there is no token associated to a ⟨𝜇𝑠+1 | 𝑗⟩, by Claim 3, there is at least one agent in ⟨𝜇𝑠+1 | 𝑗⟩ at loser, and the ⟨𝜇𝑠 |𝜇𝑠+1 ⟩ agent at winner_spreader will generate a token at it by token multiplication, which will then ascend as well. We can thus show inductively that after some point, for all 𝑠, there exists a token in one of the ⟨𝜇𝑠 |𝜇𝑠+1 ⟩, using Claim 3, token multiplication and token
Ranking Opinions with Few States in Population Protocols
ascent. (Note that token destruction cannot happen anymore as we are after Stabilization (Theorem 3.4), while token simplification ensures at least one token remains. Information spreading will then ensure that all agents in ⟨𝜇𝑠 | 𝑗⟩ for some 𝑠 ∈ [1, 𝑟 ], 𝑗 ∈ [0, 𝑘 − 1] are set to winner, blocking any further token multiplication to happen. Token simplification then ensures that there is exactly one token associated to a ⟨𝜇𝑠 |𝜇𝑠+1 ⟩ for each 𝑠. □ Proof of Theorem 4.2. The case for 𝑟 = 1 is handled by Lemma 8.2. The case for 𝑟 ≥ 2 is mostly handled by Lemma 8.3, where we conclude by noting that agents in 𝑇 set all other agents to either winner or loser correctly using information_spreading, and update their out accordingly (the key point here is that after Stabilization (Theorem 3.4), every braket ⟨𝑖 | 𝑗⟩ satisfies that there exists an 𝑠 such that [𝑖, 𝑗] 𝑘 ⊆ [𝜇𝑠 , 𝜇𝑠+1 ] 𝑘 ). The claim on the number of states is straightforward, as each agent stores a braket that can have 𝑘 2 values, a status that can have three values, and eventually an output with 𝑘 possible values. □
8.5
Proof of Theorem 4.3
Theorem 4.3 (★). Circles_TieBreak solves the relative majority problem against a weakly-fair scheduler. If there is a tie, agents all output the same color, one of the majority ones. It requires 2𝑘 3 many states, which can be reduced to 3𝑘 2 if agents are not required to output the majority color, but only whether their color wins or loses. The protocol stores three numbers between 0 and 𝑘 − 1 and the 𝑡𝑏𝑡 bit, giving 2𝑘 3 possible states. It is possible to remove the memory entry 𝑜𝑢𝑡 and add a single bit, which stores only whether and agent is in relative majority or not. For that an agent holding the tie-break token sets this bit to true for itself an all agents it meets with the same bra and to false for all other agents. This requires 3𝑘 2 states (because any agent holding a tie-break token has the output bit to 1). The overall claim follows from the following lemma. Lemma 8.4. After some number of interactions all agents store the same color in out, which is part of a (the) color in relative majority. Proof. By Theorem 3.4 after some number of interactions 𝑡 1 , the braket of every agent remains unchanged. In the corner case that 𝑡 1 = 0, meaning agents never exchange kets, only a single color is present in the population. In this case no tie-break token is ever generated and 𝑜𝑢𝑡 of all agents contains the unique color by initialization, producing the correct output. Otherwise in 𝑡 1 the last exchange of kets between agents occurs. Therefore a tie-break token is generated in 𝑡 1 . This means at least one such token exists after 𝑡 1 . It is, however, possible for multiple tokens to exist at this point, generated during previous interactions. After 𝑡 1 no more tie-break tokens are generated, because step (1) is never executed again. Step (2) destroys one token whenever two tokens meet, decreasing the overall number of tokens. Since, however, two tokens are required for it to be executed, the number of tokens can never be decreased from 1 to 0, meaning at least one token exists in every computation step after 𝑡 1 . After 𝑡 1 the weight of agents does not change anymore. The token transfer in combination with the destruction step then ensures that all tokens are eventually passed to the agent with maximum weight and among them to the one with the largest bra. If multiple agents with maximum weight
PODC ’26, July 6–10, 2026, Egham, United Kingdom
and maximum bra exist, then the destruction step still ensures that eventually only one of them holds the tie-break token. This means after some number 𝑡 2 ≥ 𝑡 1 of interactions, among all agents of maximum weight a unique agent 𝑎 exists that holds the tie-break token. Due to the output propagation, after some number 𝑡 3 ≥ 𝑡 2 of interactions, all agents store ⟨𝑖𝑎 | as output. All that is left to show is that ⟨𝑖𝑎 | represents a color in relative majority. Associate with the population sets 𝐺 1, 𝐺 2, . . . , 𝐺𝑞 as in Definition 3.1. By Lemma 3.7 after 𝑡 1 the population consists of Ð agents with brakets 𝑝 ∈ [𝑞 ] 𝑓 (𝐺 𝑝 ). Clearly 𝐺𝑞 contains all colors in relative majority. In case 𝑓 (𝐺𝑞 ) contains a single element, then this element has the largest possible weight 𝑘. Otherwise, the maximum weight is obtained in 𝑓 (𝐺𝑞 ) because 𝐺 1 ⊇ 𝐺 2 ⊇ · · · ⊇ 𝐺𝑞 . Therefore ⟨𝑖𝑎 | represents a color in relative majority, which concludes the proof. □
8.6
Proof of Theorem 5.1
Theorem 5.1 (★). Ordering solves the ordering problem with 𝑂 (𝑘 2 ) states. Formally we define the protocol as follows. Memory organization: The state of an agent 𝑎 encodes the following information: (1) 𝑙𝑑𝑎 , a single bit indicating whether 𝑎 is a leader (2) 𝑖𝑐 𝑎 the initial color of 𝑎 (in an arbitrary representation) (3) 𝑑𝑎 the label of 𝑖𝑐 𝑎 in binary representation using ⌈log2 𝑘⌉ bits Initialization: Initially every agents sets 𝑙𝑑 = 1, 𝑑 = 0, and 𝑖𝑐 is initialized with the agents initial color. Transition function: The transition function that updates the states of two agents 𝑎, 𝑏 ∈ 𝐴 is given by the following pseudocode. 1: if 𝑖𝑐 𝑎 = 𝑖𝑐𝑏 then 2: if 𝑙𝑑𝑎 = 1 and 𝑙𝑑𝑏 = 1 then 3: 𝑙𝑑𝑎 ← 0 4: if 𝑙𝑑𝑎 = 0 and 𝑙𝑑𝑏 = 1 and 𝑑𝑎 ≠ 𝑑𝑏 then 5: 𝑑𝑎 ← 𝑑𝑏 6: else 7: if 𝑑𝑎 = 𝑑𝑏 and 𝑙𝑑𝑎 = 1 and 𝑙𝑑𝑏 = 1 then 8: 𝑑𝑎 ← (𝑑𝑎 + 1) 𝑚𝑜𝑑 𝑘 Output: The output of agent 𝑎 can be read directly from 𝑑𝑎 . We show different properties of the protocol, that we will then use to argue its correctness. For any color 𝑐 ∈ 𝐶, let 𝑠𝑢𝑝𝑝 (𝑐) denote the set of agents initially supporting color 𝑐. First we consider the leader election process. Lemma 8.5. After some number of interactions 𝑡 1 each non-empty set 𝑠𝑢𝑝𝑝 (𝑐) of agents contains exactly one leader. After 𝑡 1 the leader bit of all agents will not change. Proof. The proof is highly similar to that of Lemma 1 in [26]. Some additional argumentation similar to that of proof of Lemma 7 in [16] is added. At no point does Ordering change a leader bit from 0 to 1. The number of leaders can subsequently never increase. Let #𝑐 denote the number of leaders with color 𝑐 for some 𝑐 ∈ 𝐶. When two leaders of color 𝑐 interact, one of them is set to be a non-leader, due to line 3 of the transition function, decreasing #𝑐 by exactly one. As long as there are at least two leaders of color
PODC ’26, July 6–10, 2026, Egham, United Kingdom
Breitkopf, Dallot, El-Hayek and Schmid
𝑐, #𝑐 will be decremented in that way. Two agents are required to clear a leader bit and reduce #𝑐 . Therefore no interaction reduces #𝑐 from 1 to 0 as soon as there is only a single agent left. Therefore there is exactly one leader for color 𝑐, whose leader bit will never be set to zero. This holds for any 𝑐 ∈ 𝐶, meaning there is exactly one leader per color. No leader bit of a leader can be set to 0 after that point and no leader bit of a non-leader can be set to 1. Therefore no leader bit changes anymore. □ A configuration containing a unique leader for each non-empty set 𝑠𝑢𝑝𝑝 (𝑐) of agents, in which the leader bit of no agent will ever change again, is said to be leader stable. Let 𝐿 ⊆ 𝐴 be the set of leaders in a leader stable configuration. A configuration is said to contain a valid ordering if it is leader stable and for any two leaders 𝑎, 𝑏 ∈ 𝐿, 𝑑𝑎 ≠ 𝑑𝑏 . Let 𝑚𝑑 (𝑆) denote the number of leaders with different colors having label 𝑑 in some leader stable configuration 𝑆. A label with 𝑚𝑑 (𝑆) = 0 in configuration 𝑆 is called unoccupied, unused or free. Labels with 𝑚𝑑 (𝑆) > 0 are called used or occupied. Let 𝑛𝑑 (𝑆) = 𝑚𝑎𝑥 (0, 𝑚𝑑 (𝑆) − 1). Intuitively 𝑛𝑑 describes the number of “excess leaders” having label 𝑑 ∈ 𝐾. For any 𝑑 ∈ 𝐾 and any configuration 𝑆 let: 𝑔𝑑 (𝑆) = min (ℎ − 𝑑)
mod 𝑘
ℎ∈𝐾 𝑚ℎ (𝑆 )=0
𝑅𝑑 (𝑆) = (𝑘 2 + 𝑔𝑑 (𝑆)) · 𝑛𝑑 (𝑆) In case no ℎ ∈ 𝐾 with 𝑚ℎ (𝑆) = 0 exists, define 𝑔𝑑 (𝑆) = 0. For any configuration 𝑆 further define: 𝑅(𝑆) =
𝑘 −1 ∑︁
𝑅𝑑 (𝑆)
𝑑=0
Intuitively 𝑅(𝑆) expresses “how far away” configuration 𝑆 is from containing a valid ordering. For that 𝑅𝑑 (𝑆) combines the values 𝑛𝑑 (𝑆), expressing how many excess leaders are currently using label 𝑑, with the value 𝑔𝑑 (𝑆), measuring the distance of label 𝑑 to the next unoccupied label. 𝑅𝑑 (𝑆) can therefore be thought of as (an upper bound on) the number of computation steps required by any interaction sequence starting in configuration 𝑆 to ensure all excess leaders currently using label 𝑑 are assigned some unused label. The factor 𝑘 2 takes into account that whenever a leader occupies a previously unoccupied label, the distance for all other labels to a free label increases. To readers familiar with ordinals it might help to think of the first uncountable ordinal 𝜔 instead of 𝑘 2 , expressing that an arbitrary increase in 𝑔𝑑 is compensated by a decrement by one in 𝑛𝑑 . Step by step we now show that 𝑅 will decrease until a configuration 𝑆 with 𝑅(𝑆) = 0 is reached, at which point a valid ordering exists and 𝑅 will never increase again. First we show that 𝑅(𝑆) = 0 corresponds to a valid ordering in 𝑆. Lemma 8.6. 𝑅(𝑆) = 0 for a leader stable configuration 𝑆 ⇐⇒ There is a valid ordering in configuration 𝑆. Proof. ( =⇒ ) Assume 𝑅(𝑆) = 0 for some leader stable configuration 𝑆. By definition of 𝑛𝑑 and 𝑔𝑑 it holds that 𝑛𝑑 (𝑆) ≥ 0 and 𝑔𝑑 (𝑆) ≥ 0 ∀𝑑 ∈ 𝐾. The number of colors 𝑘 ≥ 1 and thus also 𝑘 2 is
a positive constant. Therefore 𝑅(𝑆) = 0 implies 𝑛𝑑 (𝑆) = 0 ∀𝑑 ∈ 𝐾. For any label 𝑑 there are therefore zero or one leaders having label 𝑑. This implies for any two leaders 𝑎, 𝑏 ∈ 𝐿, 𝑑𝑎 ≠ 𝑑𝑏 . 𝑆 therefore contains a valid ordering. ( ⇐= ) Assume 𝑆 contains a valid ordering. By definition 𝑆 is leader stable. As it contains a valid ordering, there are no two agents 𝑎, 𝑏 ∈ 𝐿, s.t. 𝑑𝑎 = 𝑑𝑏 . This means 𝑚𝑑 (𝑆) < 2 ∀𝑑 ∈ 𝐾, implying 𝑛𝑑 (𝑆) = 0 ∀𝑑 ∈ 𝐾 and thus 𝑅(𝑆) = 0. □ We show next that as long as the value of 𝑅 is larger than zero there is some edge in the interaction graph that a scheduler might select, such that the value of 𝑅 decreases. This is because as long as 𝑅 is non-zero there are two leaders using the same label. Once they interact one of them selects a new label. Either it chooses one that no other leader is using or it at least gets closer to such an unoccupied label. Both options reduce 𝑅. Lemma 8.7. For any leader stable configuration 𝑆 with 𝑅(𝑆) > 0, there exists an interaction (𝑎, 𝑏), such that for configuration 𝑆 ′ with (𝑎,𝑏 )
𝑆 −−−−→ 𝑆 ′ it holds that 𝑅(𝑆 ′ ) < 𝑅(𝑆). Proof. For 𝑅(𝑆) > 0 to hold there must be some 𝑑 ∈ 𝐾, such that 𝑛𝑑 (𝑆) > 0. This implies 𝑚𝑑 (𝑆) ≥ 2, meaning there are at least two leaders 𝑎 and 𝑏 using label 𝑑. Consider the interaction between 𝑎 and 𝑏. In 𝑆 they both share label 𝑑. The interaction causes 𝑎 to update its label to (𝑑 + 1) mod 𝑘 (for a shorter notation the mod 𝑘 operation will be suppressed in the rest of the proof). Therefore 𝑛𝑑 (𝑆 ′ ) = 𝑛𝑑 (𝑆) − 1, because in 𝑆 ′ one leader less uses 𝑑 than in 𝑆. There are two possible cases that can arise. Either the new label of 𝑎 was unoccupied, meaning 𝑚𝑑+1 (𝑆) = 0 or it was already occupied, meaning 𝑚𝑑+1 (𝑆) > 0. For convenience define the sum of excess leaders: 𝑘 −1 ∑︁ 𝑃 (𝑆) = 𝑛𝑑 ′ (𝑆) 𝑑 ′ =0
Case 𝑚𝑑+1 (𝑆) = 0: Let 𝑅(𝑆) − 𝑅(𝑆 ′ ) = Δ𝑅 be the difference between 𝑅(𝑆) and 𝑅(𝑆 ′ ). Express Δ𝑅 as Δ𝑅 = Δ𝑅 + − Δ𝑅 − with Δ𝑅 + ≥ 0 being the sum of all terms that decrease the value of 𝑅(𝑆 ′ ) compared to 𝑅(𝑆), meaning they increase the difference between them, and with Δ𝑅 − ≥ 0 being the sum of all therms that increase the value of 𝑅(𝑆 ′ ) compared to 𝑅(𝑆), meaning they decrease the difference. The assumption 𝑚𝑑+1 (𝑆) = 0 implies 𝑚𝑑+1 (𝑆 ′ ) = 1 and therefore 𝑛𝑑+1 (𝑆) = 𝑛𝑑+1 (𝑆 ′ ) = 0. In 𝑆 no agent was using label 𝑑 + 1 and in configuration 𝑆 ′ only agent 𝑎 is using it. Therefore in both 𝑆 and 𝑆 ′ there are no excess leaders in label 𝑑. As mentioned above 𝑛𝑑 (𝑆 ′ ) = 𝑛𝑑 (𝑆) − 1. The value 𝑛𝑑 ′′ for all other labels 𝑑 ′′ ∈ 𝐾 remains unaffected by the interaction. Therefore 𝑃 (𝑆 ′ ) = 𝑃 (𝑆) − 1, meaning the overall number of leaders that must select a different label decreases by one. This implies Δ𝑅 + ≥ 𝑘 2 , because 𝑘 2 is added to the sum one time less and the difference between 𝑅(𝑆) and 𝑅(𝑆 ′ ) is therefore increased by a value of at least 𝑘 2 . Because 𝑑 + 1 is not a free label anymore in 𝑆 ′ , for every label ′ 𝑑 ∈ 𝐾 the value of 𝑔𝑑 ′ (𝑆 ′ ) might increase compared to the value of 𝑔𝑑 ′ (𝑆). Considering the range of 𝑔𝑑 ′ the value can increase by at most 𝑘 −1. With 𝑘 many leaders this means Δ𝑅 − ≤ 𝑘 (𝑘 −1) = 𝑘 2 −𝑘,
Ranking Opinions with Few States in Population Protocols
because at most 𝑘 times the value of 𝑘 − 1 is added to the sum3 , decreasing the difference in 𝑅(𝑆) and 𝑅(𝑆 ′ ) by at most 𝑘 2 − 𝑘. It now therefore holds that Δ𝑅 = Δ𝑅 + − Δ𝑅 − ≥ 𝑘 2 − (𝑘 2 − 𝑘) = 𝑘 > 1. Therefore 𝑅(𝑆) > 𝑅(𝑆 ′ ). Case 𝑚𝑑+1 (𝑆) > 0: In this case it holds that 𝑛𝑑+1 (𝑆 ′ ) = 𝑛𝑑+1 (𝑆) +
1, meaning in 𝑆 there already was at least one agent using label 𝑑 + 1 and in configuration 𝑆 ′ there is now one more. Together with 𝑛𝑑 (𝑆 ′ ) = 𝑛𝑑 (𝑆) − 1 this means 𝑃 (𝑆 ′ ) = 𝑃 (𝑆), meaning the number of leaders that must select a new label remains unchanged. We now argue that ∀𝑑 ′ ∈ 𝐾 : 𝑔𝑑 ′ (𝑆) = 𝑔𝑑 ′ (𝑆 ′ ), meaning the distance to the next free label does not change for any label. It holds that 𝑚𝑑 (𝑆) ≥ 2 and 𝑚𝑑 (𝑆 ′ ) ≥ 1. Also it holds that 𝑚𝑑+1 (𝑆) ≥ 1 and 𝑚𝑑+1 (𝑆 ′ ) ≥ 2. Neither of the labels 𝑑 and 𝑑 + 1 was unoccupied in 𝑆 and neither is in 𝑆 ′ . For all other labels 𝑑 ′ ∈ 𝐾 \ {𝑑, 𝑑 + 1} : 𝑚𝑑 ′ (𝑆) = 𝑚𝑑 ′ (𝑆 ′ ). Interaction (𝑎, 𝑏) thus did not lead to any previously occupied label being unoccupied or to any unoccupied label being occupied, therefore it did not change the distance to the next free label for any 𝑑 ∈ 𝐾. Because 𝑅(𝑆) > 0 and because there are 𝑘 many labels and at most 𝑘 many leaders, there must be some free label. The fact that 𝑚𝑑 (𝑆) > 0 and 𝑚𝑑+1 (𝑆) > 0 implies 𝑔𝑑 (𝑆) = 𝑔𝑑+1 (𝑆) + 1. This means that because both labels 𝑑 and 𝑑 + 1 are used in 𝑆, the next free label is one step further away for 𝑑 than it is for 𝑑 + 1. Define 𝑝 = 𝑔𝑑 (𝑆). Then 𝑔𝑑+1 (𝑆) = 𝑝 − 1 and as argued before 𝑔𝑑 (𝑆 ′ ) = 𝑝 and 𝑔𝑑+1 (𝑆 ′ ) = 𝑝 − 1. Now consider the following two terms: 𝑅𝑑 (𝑆 ′ ) + 𝑅𝑑+1 (𝑆 ′ ) = 𝑛𝑑 (𝑆 ′ )(𝑘 2 + 𝑝) + 𝑛𝑑+1 (𝑆 ′ )(𝑘 2 + 𝑝 − 1) = (𝑛𝑑 (𝑆) − 1)(𝑘 2 + 𝑝) + (𝑛𝑑+1 (𝑆) + 1)(𝑘 2 + 𝑝 − 1) 𝑅𝑑 (𝑆) + 𝑅𝑑+1 (𝑆) = 𝑛𝑑 (𝑆)(𝑘 2 + 𝑝) + 𝑛𝑑+1 (𝑆)(𝑘 2 + 𝑝 − 1) Subtracting 𝑅𝑑 (𝑆 ′ ) + 𝑅𝑑+1 (𝑆 ′ ) from 𝑅𝑑 (𝑆) + 𝑅𝑑+1 (𝑆) gives: 𝑅𝑑 (𝑆) + 𝑅𝑑+1 (𝑆) − (𝑅𝑑 (𝑆 ′ ) + 𝑅𝑑+1 (𝑆 ′ )) = 𝑘 2 + 𝑝 − (𝑘 2 + 𝑝 − 1) = 1 It further holds that ∀𝑑 ′ ∈ 𝐾 \ {𝑑, 𝑑 + 1} : 𝑅𝑑 ′ (𝑆) = 𝑅𝑑 ′ (𝑆 ′ ), because 𝑑 ′ stays unaffected by the interaction. It overall follows that 𝑅(𝑆 ′ ) < 𝑅(𝑆). □ As long as 𝑅 is non-zero, there is some interaction that decreases 𝑅. We now show that for all configurations there is never any interaction that increases 𝑅. Lemma 8.8. For any leader stable configuration 𝑆 and interaction (𝑎,𝑏 )
𝑆 −−−−→ 𝑆 ′ it holds that 𝑅(𝑆 ′ ) ≤ 𝑅(𝑆). Proof. Consider any operation of the transition function that may be executed on the interaction (𝑎, 𝑏). Case 𝑖𝑐 𝑎 = 𝑖𝑐𝑏 : Only the label of a non-leader may be changed in this case. Non-leaders do not influence the value of 𝑅 in any way, implying 𝑅(𝑆) = 𝑅(𝑆 ′ ). Case 𝑖𝑐 𝑎 ≠ 𝑖𝑐𝑏 : If 𝑑𝑏 ≠ 𝑑𝑎 or 𝑙𝑑𝑎 = 0 or 𝑙𝑑𝑏 = 0, then the state of 3 This is very crude estimate, as obviously not for all 𝑘 leaders the distance can be
increased by 𝑘 − 1 at the same time. A tighter analysis would allow to choose a constant smaller than 𝑘 2 in the definition of 𝑅 (𝑆 ) but would otherwise have no other consequences for the proof.
PODC ’26, July 6–10, 2026, Egham, United Kingdom
𝑎 and 𝑏 remains unchanged, meaning 𝑅(𝑆) = 𝑅(𝑆 ′ ). Otherwise 𝑑𝑎 will be changed to 𝑑𝑎′ = (𝑑𝑎 + 1) 𝑚𝑜𝑑 𝑘. By Lemma 8.7 this implies 𝑅(𝑆 ′ ) < 𝑅(𝑆). □ With all the above lemmata defined, we show correctness of Ordering. Theorem 5.1 (★). Ordering solves the ordering problem with 𝑂 (𝑘 2 ) states. Proof. After some number of interactions 𝑡 1 Ordering reaches a leader stable configuration 𝑆𝑡1 according to Lemma 8.5. At that point 𝑅(𝑆𝑡1 ) can be defined. Obviously 𝑅(𝑆𝑡1 ) is a finite value. We show by induction over all possible values of 𝑅(𝑆𝑡1 ), that eventually a configuration 𝑆𝑡2 will be reached with 𝑅(𝑆𝑡2 ) = 0. Induction base: 𝑅(𝑆𝑡1 ) = 0. In this case 𝑡 1 = 𝑡 2 and the claim obviously holds. Induction hypothesis: Ordering eventually reaches a configuration 𝑆𝑡2 with 𝑅(𝑆𝑡2 ) = 0, when at 𝑡 1 , 𝑅(𝑆𝑡1 ) = 𝑥 ≥ 0. Induction step: To show: Ordering eventually reaches a configuration 𝑆𝑡2 with 𝑅(𝑆𝑡2 ) = 0, when at 𝑡 1 , 𝑅(𝑆𝑡1 ) = 𝑥 + 1. According to Lemma 8.7 there exists some interaction (𝑎, 𝑏), such (𝑎,𝑏 )
that 𝑆𝑡1 −−−−→ 𝑆𝑡1 +1 and 𝑅(𝑆𝑡1 +1 ) < 𝑅(𝑆𝑡1 ). By Lemma 8.8 no interaction any scheduler might select increases 𝑅. Looking at the proof of Lemma 8.8 more closely it clearly also follows that any interaction that does not decrease 𝑅, does not change the state of any leader. Therefore no matter how often a scheduler may select any interaction that does not decrease 𝑅, leading to some configuration 𝑆𝑡′1 , the interaction (𝑎, 𝑏) still produces a configuration (𝑎,𝑏 )
𝑆𝑡′1 +1 such that 𝑆𝑡′1 −−−−→ 𝑆𝑡′1 +1 and 𝑅(𝑆𝑡′1 +1 ) < 𝑅(𝑆𝑡′1 ) = 𝑅(𝑆𝑡1 ). A weakly fair scheduler (as well as a random or a globally fair one) will therefore eventually either select interaction (𝑎, 𝑏) or another one reducing 𝑅. Therefore eventually 𝑅 will be decreased and by induction hypothesis a configuration 𝑆𝑡2 with 𝑅(𝑆𝑡2 ) = 0 will be reached. Obviously 𝑅 can never get negative. Using Lemma 8.8 again therefore after 𝑡 2 , 𝑅 will never increase and thus remain zero. In 𝑆𝑡2 there is a valid ordering on the leaders, according to Lemma 8.6. After 𝑡 2 the only state changes that will occur are those of non-leaders interacting with the leaders of their color, causing the non-leader to copy the label of the leader, until finally in some configuration 𝑆𝑡3 , all agents of the same color agree on the same binary label, which is different from the labels of all other colors. Ordering stores the initial color of an agent, for which there are 𝑘 options at most, the label associated with that color, again having at most 𝑘 options, and a single bit indicating whether the agent is a leader. This gives 2𝑘 2 ∈ 𝑂 (𝑘 2 ) possible states. □
8.7
Proof of Theorem 5.2
Theorem 5.2 (★). Ord-Circles solves relative majority in the unordered setting against a weakly-fair scheduler using 𝑂 (𝑘 4 ) states. This can be reduced to 𝑂 (𝑘 3 ) many states if every agent is only required to report whether their color wins or loses.
PODC ’26, July 6–10, 2026, Egham, United Kingdom
Breitkopf, Dallot, El-Hayek and Schmid
We will first show properties of Ord-Circles, before ultimately arguing for its correctness. On a high level the proof works as follows. Every operation the ordering step intends to make on an agent’s bra is eventually carried out and corresponds precisely to ordering protocol Ordering. The steps are carried out after a finite number of interactions and in a way that preserves correctness of sub-protocol Circles. Once the ordering converges only Circles is run and the overall process stabilizes. We subdivide this argument further into smaller parts. First we show that Ord-Circles preserves Circles’s invariant. This is crucial to later argue for the overall convergence of Ord-Circles Lemma 8.9. Ord-Circles maintains Invariant 3.3, meaning in Ord-Circles for every 𝑖 ∈ 𝐾, there are as many bras ⟨𝑖 | in the population, as there are kets |𝑖⟩. Proof. Step (1) does not change the braket of any agent and therefore does not influence the invariant. Step (5) updates the braket of agents according to Circles, which preserves the invariant. Left to consider are therefore steps (2), (4) and (3). Step (2) re-initializes pending agent 𝑎. Any pending agent is consistent, because of the following. Step (4) is the only way for an agent to be put into ordering state 𝐶𝐿. For that is must be consistent and in ordering state 𝐶𝐿𝑊 . Only non-leaders are put into ordering state 𝐶𝐿𝑊 in step (1). An agent in ordering state 𝐶𝐿, being a non-leader, only interacts using step (2), which re-initializes it. Therefore as long it is pending, it remains consistent. The braket of 𝑎 therefore has the form ⟨𝑖𝑎 |𝑖𝑎 ⟩ for some 𝑖𝑎 . After re-initializing 𝑎 stores ⟨𝑖𝑏 |𝑖𝑏 ⟩. Step (2) therefore removes a matching braket pair and adds a matching braket pair to the population. This clearly preserves Invariant 3.3. Step (4) re-initializes consistent agent 𝑎 with braket ⟨𝑖𝑎 |𝑖𝑎 ⟩ to ⟨(𝑖𝑎 + 1) mod 𝑘 |(𝑖𝑎 + 1) mod 𝑘⟩. As before one matching braket pair is removed and one added, preserving the invariant. Step (3) exchanges the kets of two agents, obviously preserving the Invariant. The overall claim therefore holds. □ Next we consider the leader election process within the ordering routine to simplify subsequent proofs. Lemma 8.10. After some number of interactions there is a unique leader in every set of agents initially supporting the same color. Afterwards the leader bit of no agent changes. Proof. See proof of Lemma 8.5
□
We again say a configuration is leader stable if it contains a unique leader per color in the population and the leader bit of no agent can change anymore. Once such a configuration is reached, further important observations can be made about the population. Lemma 8.11. After a leader stable configuration is reached, the ordering state of any agent changes only finitely often. Proof. Again we call some label 𝑖 ∈ 𝐾 used in case there exists a leader that stores the label as its bra and free otherwise. A leader can never be in ordering state 𝐶𝐿 or 𝐶𝐿𝑊 . To put a leader 𝑎 into ordering state 𝑜𝑠𝑎 = 𝐼 , it must interact with some leader 𝑏 with the same bra and 𝑜𝑠𝑏 = 𝑈 . In this interaction ordering state and bra of 𝑏 remain unchanged. Only leaders with ordering state 𝐼 ever change their bra. Therefore once a label is used by some leader, it
will never be free, because two leaders using the label are required to put one of them into ordering state 𝐼 , while ordering state and bra of the other one remain unaffected by the interaction. Now assume there was some leader 𝑎 that was changed from ordering state 𝑈 to ordering state 𝐼 𝑘 many times. Then 𝑎 must have increased its label 𝑘 − 1 times, as a leader can go from ordering state 𝐼 to ordering state 𝑈 only using step (4). This means 𝑎 used every label once at some point. As described above no label that was once used by some leader will ever become free again. Therefore all the labels are used. However, 𝑎 goes into ordering state 𝐼 a 𝑘 th time, meaning there are at least two leaders in the last label 𝑎 chose. Overall this means for every label there is at least one leader using it and there is a label that at least two leaders use. This means there are more than 𝑘 leaders, which is a contradiction, because, as shown before, in a leader stable configuration there are as many leaders as there are colors and there are at most 𝑘 colors. This contradiction implies that leaders only go into ordering state 𝐼 at most 𝑘 − 1 times and therefore only change their bra at most 𝑘 − 1 times. Since leaders can only alternate between ordering states 𝑈 and 𝐼 , they therefore change their ordering state only finitely often. Some non-leader 𝑎 goes from ordering state 𝑈 into 𝐶𝐿𝑊 only in case the leader 𝑏 of its color changed its label since 𝑎 last interacted with it. As just shown leaders change their label at most 𝑘 − 1 many times and therefore non-leaders go into state 𝐶𝐿𝑊 at most 𝑘 − 1 times and therefore also only update their label at most 𝑘 − 1 times. Non-leaders can go from ordering state 𝑈 to 𝐶𝐿𝑊 to 𝐶𝐿 to 𝑈 again, but not backwards. They therefore only update their states finitely often. □ The argument above is crucial to now argue that agents do not wait indefinitely to become consistent. This is important because only consistent agents can be re-initialized with a new bra. Lemma 8.12. Any inconsistent and unstable agent 𝑎 eventually becomes consistent. Proof. Let 𝑎 be an inconsistent and unstable agent. This means the braket of 𝑎 contains ⟨𝑖𝑎 | 𝑗𝑎 ⟩ with 𝑖𝑎 ≠ 𝑗𝑎 . For contradiction assume 𝑎 remains inconsistent throughout the computation. By Invariant 3.3, there exists some agent 𝑏 with braket ⟨𝑖𝑏 | 𝑗𝑏 ⟩, such that 𝑖𝑏 ≠ 𝑗𝑏 = 𝑖𝑎 . For every configuration let 𝐵 be the set of nonpending agents with 𝑖𝑎 as ket. We will now argue that under a weakly fair scheduler 𝑎 eventually interacts with an agent from 𝐵. By weak fairness 𝑎 interacts with all other agents infinitely often. Also, as long as 𝑎 is inconsistent, 𝐵 always contains some other agent. According to Lemma 8.11 no agent changes its ordering state infinitely often. Clearly this also holds in case we assume 𝑎 (and potentially other agents) to remain inconsistent throughout the computation, because in case 𝑎 is a non-leader it cannot make other agents unstable and in case 𝑎 is a leader, it cannot make leaders of different color unstable (since for that it would need to be stable) and can make non-leaders of its color unstable only once (since it does not change its 𝑏𝑟𝑎). This means after some number of interactions either 𝑎 interacted with some agent in 𝐵 or 𝑎 remains inconsistent, but none of the other agents change their ordering state anymore. All agents then only interact using step (5) of Ord-Circles, as all other steps update the ordering state of at least one agent. By correctness of Circles therefore eventually the braket of all agents
Ranking Opinions with Few States in Population Protocols
PODC ’26, July 6–10, 2026, Egham, United Kingdom
stabilizes, meaning no agents exchange their kets anymore (even in case pending vertices exist as they are consistent and can safely be ignored). At this point weak fairness guarantees that 𝑎 interacts with some agent in 𝐵. Step (3) will be executed, making 𝑎 consistent, which produces a contradiction. No other step of Ord-Circles can change 𝑜𝑠𝑎 before 𝑎 is consistent. □
values 𝑙𝑑𝑎 , 𝑜𝑠𝑎 and the bits for breaking, sharing and reporting ties can take a constant number of different values. This overall gives 𝑂 (𝑘 4 ) possible states. Removing 𝑜𝑢𝑡 and adding a single bit storing whether an agent is in relative majority or not, this can be reduced to 𝑂 (𝑘 3 ) for versions with binary win-lose output. □
With all the above arguments in place we can now argue that the sub-protocol Ordering actually converges within Ord-Circles.
8.8
Lemma 8.13. After some number of interactions for all pairs of agents 𝑎, 𝑏 ∈ 𝐴 it holds that ⟨𝑖𝑎 | = ⟨𝑖𝑏 | ⇐⇒ 𝑖𝑐 𝑎 = 𝑖𝑐𝑏 . All agents are in ordering state 𝑜𝑠 = 𝑈 . Both bra and 𝑜𝑠 of no agent subsequently changes. Proof. Step (1) puts a leader into ordering state 𝐼 exactly in case Ordering would increment its label, namely in case there is another (stable) leader with of different color using the same bra. Whenever an agent is put into ordering state 𝐼 , then it either is consistent or by Lemma 8.12 eventually will be. At that point step (4) carries out the increment modulo 𝑘 and puts the agent back into ordering state 𝑈 . Step (1) puts a non-leader into ordering state 𝐶𝐿𝑊 exactly in case Ordering would copy the label of its leader, namely in case its leader changed its bra since they last interacted (and the agent is not already trying to carry out a copy operation). Again either the agent already is consistent or it eventually will be, at which point step (4) and then step (2) ensure it copies its leaders label and sets its ordering state to 𝑈 . By correctness of the ordering protocol Ordering, therefore eventually for two agents 𝑎, 𝑏 ∈ 𝐴 it holds that ⟨𝑖𝑎 | = ⟨𝑖𝑏 | if and only if they store the same initial color. On the last increment or copy operation all agents set 𝑜𝑠 = 𝑈 . With all agents of the same initial color sharing the same bra, no agent can subsequently be put into ordering state 𝐶𝐿𝑊 and therefore also not into ordering state 𝐶𝐿. With all agents of different color having different bras, no agent can be put into ordering state 𝐼 . Therefore all agents store ordering state 𝑈 . □ Having shown that an ordering on the colors is eventually established, we now arrive at the final theorem. Theorem 5.2 (★). Ord-Circles solves relative majority in the unordered setting against a weakly-fair scheduler using 𝑂 (𝑘 4 ) states. This can be reduced to 𝑂 (𝑘 3 ) many states if every agent is only required to report whether their color wins or loses. Proof. According to Lemma 8.13 after some number 𝑡 1 of interactions, the ordering process converges, 𝑜𝑠 = 𝑈 for all agents and ⟨𝑖𝑎 | = ⟨𝑖𝑏 | ⇐⇒ 𝑖𝑐 𝑎 = 𝑖𝑐𝑏 . At that point only step (5) of Ord-Circles is executed, meaning only Circles is used. Because Invariant 3.3 of Circles is maintained, according to Lemma 8.9, Circles converges for the final distribution of bras. This means after some number 𝑡 2 ≥ 𝑡 1 of interactions all agents agree on the bra in relative majority and therefore on the initial color in relative majority. As described before the output can be adapted to contain a color instead of a label. For some agent 𝑎, Ord-Circles stores 𝑖𝑐 𝑎 , ⟨𝑖𝑎 | 𝑗𝑎 ⟩, 𝑜𝑢𝑡𝑎 , 𝑙𝑑𝑎 , 𝑜𝑠𝑎 and some number of bits to handle reporting, sharing or breaking of ties. The values 𝑖𝑐 𝑎 , 𝑖𝑎 , 𝑗𝑎 and 𝑜𝑢𝑡𝑎 can take 𝑘 values each. All
Proof of Lemma 6.5
Proof. Rule (2) cannot modify any agents as there are no two tokens on kets with the same color. Rule (3) cannot modify any agents as there are no two tokens associated to the same ranking. Rule (4) cannot modify any agents as for every 𝑖, all bras and kets have the same ranking r(𝑖). Rule (5) cannot modify any agents by Lemma 6.2. Rule (6) cannot modify any agents as the token for 𝑖 with r(𝑖) = 0 is on a braket ⟨𝑖, r(𝑖) = 0|r(𝑖) = 0, 𝑖⟩ ∗ which minimizes the ranking in the bra, while for all 𝑗 ≠ 𝑖, we have that the kets containing 𝑗 are all of the same form: ⟨ℓ, r(ℓ)|r( 𝑗) = r(ℓ) + 1, 𝑗⟩, since a token is not transferred between agents of same braket. Finally, Rule (7) cannot modify any agents, as there are two tokens on brakets with bra of ranking 0 one of which is of the form ⟨𝑖, r(𝑖) = 0|r(𝑖) = 0, 𝑖⟩ ∗ , while all others are on brakets of bras of different weights. The two tokens on the same bra cannot interact because one of them has the same bra and ket, while any other pair of tokens cannot interact because they have different bras. □
8.9
Proof of Lemma 6.12
Proof. In the particular configuration 𝐸 ℓ −1 , none of the rules (2) to (5) apply. It thus remains to show how Rules (6) and (7) are useful. We know that in configuration 𝐸 ℓ −1 , the ℓ −1 most popular colors have the correct assigned ranking, that is, |r( 𝑗), 𝑗⟩ ∗ exists in the configuration for all 𝑗 ≤ ℓ − 1, and the Circles protocol has stabilized. Let 𝑢 be the ℓ-th most popular color, and 𝑣 be the one assigned rank ℓ in 𝐸 ℓ −1 . If 𝑢 = 𝑣, then we are already in configuration 𝐸 ℓ and there is nothing to prove. We thus assume that 𝑢 ≠ 𝑣. Let 𝑖 1, . . . , 𝑖 ℓ −1 be the ℓ −1 most popular colors. Since the Circles protocol is stabilized, we know that there is a greedy independent set with the elements 𝑖 1, . . . , 𝑖 ℓ −1, 𝑢. • If ℓ = 0, then this is simply one element, and there is a braket ⟨𝑢, 𝔲|𝔲, 𝑢⟩ ◦ . Through Rule (6), this braket can get the token for 𝑢, and through Rule (7), can obtain a newly assigned ranking of 0. • Otherwise, if ℓ ≠ 0, since 𝑥𝑖 ℓ −1 > 𝑥𝑢 , we have that every greedy independent set containing 𝑢 also contains 𝑖 ℓ −1 . Therefore, coupled with the fact that there exists a greedy independent set with 𝑖 1, . . . , 𝑖 ℓ −1, 𝑢, the bra with smallest ranking associated to a ket of the form |·, 𝑢⟩ is ⟨𝑖 ℓ −1, ℓ − 1|. Through Rule (6), this braket ⟨𝑖 ℓ −1, ℓ − 1|·, 𝑢⟩ can get the token for 𝑢. Similarly, we have that every greedy independent set containing 𝑣 also contains 𝑖 ℓ −1 . Therefore, coupled with the fact that there exists a greedy independent set with 𝑖 1, . . . , 𝑖 ℓ −1, 𝑣, . . . , the bra with smallest ranking associated to a ket of the form |ℓ, 𝑣⟩ is ⟨𝑖 ℓ −1, ℓ − 1|. Through Rule (6), this braket ⟨𝑖 ℓ −1, ℓ − 1|ℓ, 𝑣⟩ can get the token for 𝑣. And thus through Rule (7), ⟨𝑖 ℓ −1, ℓ − 1|·, 𝑢⟩ ∗ and ⟨𝑖 ℓ −1, ℓ − 1|ℓ, 𝑣⟩ ∗ meet and exchange rankings, with 𝑢 getting the ranking ℓ = r(𝑢). The tokens who have had their rankings changed can now broadcast the new value of their rankings through Rule (4), and then any
PODC ’26, July 6–10, 2026, Egham, United Kingdom
steps needed to stabilize the Circles protocol can happen through Rule (5). □
Breitkopf, Dallot, El-Hayek and Schmid