Order statistics in population protocols via simple dynamics D'Archivio, Niccolò Almahmoud, Hind Natale, Emanuele Mallmann-Trenn, Frederik ddc:000 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. Association for Computing Machinery 2026 info:eu-repo/semantics/conferenceObject doc-type:conferenceObject text http://purl.org/coar/resource_type/c_5794 https://research-explorer.ista.ac.at/record/22368 https://research-explorer.ista.ac.at/download/22368/22379 D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. Order statistics in population protocols via simple dynamics. In: <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>. Association for Computing Machinery; 2026:425-436. doi:<a href="https://doi.org/10.1145/3796701.3815922">10.1145/3796701.3815922</a> eng info:eu-repo/semantics/altIdentifier/doi/10.1145/3796701.3815922 info:eu-repo/semantics/altIdentifier/isbn/9798400725128 https://creativecommons.org/licenses/by/4.0/ info:eu-repo/semantics/openAccess