@inproceedings{22368,
  abstract     = {We study simple dynamics in the population protocol model, in
which 𝑛 agents start with totally ordered initial opinions 𝑥1, 𝑥2, . . . ,
𝑥𝑛 and, in each round, a randomly chosen agent changes its opinion
as a function of the opinion of other randomly chosen agents. Such
dynamics often converge to consensus on a single fixation value 𝑋ˆ.
This paper asks how to control the distribution of 𝑋ˆ as a randomised
choice among the initial opinions by designing suitable simple
dynamics. Writing the sorted initial values as 𝑥(1) ≤ · · · ≤ 𝑥(𝑛)
,
we design two protocols that realise natural target laws over order
statistics.
First, for a parameter 𝑝 ∈ (0, 1), our geometric protocol biases
toward larger opinions and satisfies P

𝑋ˆ = 𝑥(𝑘)

∝ 𝑝
𝑛−𝑘
, for
𝑘 = 1, . . . , 𝑛. Equivalently, P

𝑋ˆ = 𝑥(𝑘)

= (1 − 𝑝)𝑝
𝑛−𝑘
/(1 − 𝑝
𝑛
).
Second, our binomial protocol assigns a shifted binomial law to the
ranks in ascending order: if 𝐾 −1 ∼ Bin(𝑛−1, 1−𝑝), then 𝑋ˆ = 𝑥(𝐾)
,
i.e., P

𝑋ˆ = 𝑥(𝑘)

=
𝑛−1
𝑘−1


𝑝
𝑛−𝑘
(1 − 𝑝)
𝑘−1
, for 𝑘 = 1, . . . , 𝑛.
Applications of this include computing the Top-𝑘 values for
small 𝑘 on general interaction graphs. A central contribution of
this work is that, in contrast to most population protocols, we can
characterise the fixation distribution in closed form. This is enabled
by a novel analysis technique, which also yields applications: we
derive new results for the Median protocol that extend the state of
the art.},
  author       = {D'Archivio, Niccolò and Almahmoud, Hind and Natale, Emanuele and Mallmann-Trenn, Frederik},
  booktitle    = {Proceedings of the Annual ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400725128},
  location     = {Egham, United Kingdom},
  pages        = {425--436},
  publisher    = {Association for Computing Machinery},
  title        = {{Order statistics in population protocols via simple dynamics}},
  doi          = {10.1145/3796701.3815922},
  year         = {2026},
}

@inproceedings{22367,
  abstract     = {We study the Undecided-State Dynamics (USD), a fundamental consensus process in which each vertex holds one of k decided opinions or the undecided state. We consider both the gossip model and the population protocol model. Prior work established tight bounds on the consensus time of this process only for the regime 
k
=
O
(
n
/
(
log
⁡
n
)
2
)
 (for the population protocol model) and k = O((n/log n)1/3) (for the gossip model), often under restrictive assumptions on the initial configuration.
In this paper, we obtain the first consensus-time guarantees for USD that hold for arbitrary 2 ≤ k ≤ n and for arbitrary initial configurations in both the gossip model and the population protocol model. In the gossip model, USD reaches consensus within 
O
~
(
min
{
k
,
n
}
)
 synchronous rounds with probability 1 - p⊥ - n-c, where p⊥ is the gossip-specific probability of collapsing to the all-undecided state in the first round. In the population protocol model, USD reaches consensus within 
O
~
(
min
{
k
n
,
n
3
/
2
}
)
 asynchronous interactions with high probability. We also present lower bounds that match the upper bounds up to polylogarithmic factors for a specific initial configuration and show that our upper bounds are essentially optimal.},
  author       = {Cooper, Colin and Mallmann-Trenn, Frederik and Radzik, Tomasz and Shimizu, Nobutaka and Shiraga, Takeharu},
  booktitle    = {Proceedings of the Annual ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400725128},
  keywords     = {consensus dynamics, undecided state dynamics, gossip model, population protocol model},
  location     = {Egham, United Kingdom},
  pages        = {77--87},
  publisher    = {Association for Computing Machinery},
  title        = {{Undecided state dynamics with many opinions}},
  doi          = {10.1145/3796701.3815920},
  year         = {2026},
}

@inproceedings{22327,
  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.},
  author       = {Breitkopf, Tom-Lukas and Dallot, Julien and El-Hayek, Antoine and Schmid, Stefan},
  booktitle    = {Proceedings of the ACM Symposium on Principles of Distributed Computing},
  isbn         = {9798400725128},
  location     = {Egham, United Kingdom},
  pages        = {414 -- 424},
  publisher    = {Association for Computing Machinery},
  title        = {{Ranking opinions with few states in population protocols}},
  doi          = {10.1145/3796701.3815913},
  year         = {2026},
}