@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},
}