conference paper published yes Niccolò D'Archivio author Hind Almahmoud author Emanuele Natale author Frederik Mallmann-Trenn author 68748c44-84d5-11f1-b4f6-ca083374e553 MoHe department PODC: Symposium on Principles of Distributed Computing 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. https://research-explorer.ista.ac.at/download/22368/22379/2026_ACMPODC_dArchivio.pdf application/pdfno Association for Computing Machinery2026Egham, United Kingdom eng 979840072512810.1145/3796701.3815922 425-436 N. D’Archivio, H. Almahmoud, E. Natale, F. Mallmann-Trenn, in:, Proceedings of the Annual ACM Symposium on Principles of Distributed Computing, Association for Computing Machinery, 2026, pp. 425–436. D’Archivio N, Almahmoud H, Natale E, Mallmann-Trenn F. 2026. Order statistics in population protocols via simple dynamics. Proceedings of the Annual ACM Symposium on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed Computing, 425–436. D’Archivio, N., Almahmoud, H., Natale, E., &#38; Mallmann-Trenn, F. (2026). Order statistics in population protocols via simple dynamics. In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 425–436). Egham, United Kingdom: Association for Computing Machinery. <a href="https://doi.org/10.1145/3796701.3815922">https://doi.org/10.1145/3796701.3815922</a> 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> D’Archivio, Niccolò, et al. “Order Statistics in Population Protocols via Simple Dynamics.” <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association for Computing Machinery, 2026, pp. 425–36, doi:<a href="https://doi.org/10.1145/3796701.3815922">10.1145/3796701.3815922</a>. N. D’Archivio, H. Almahmoud, E. Natale, and F. Mallmann-Trenn, “Order statistics in population protocols via simple dynamics,” in <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 425–436. D’Archivio, Niccolò, Hind Almahmoud, Emanuele Natale, and Frederik Mallmann-Trenn. “Order Statistics in Population Protocols via Simple Dynamics.” In <i>Proceedings of the Annual ACM Symposium on Principles of Distributed Computing</i>, 425–36. Association for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3796701.3815922">https://doi.org/10.1145/3796701.3815922</a>. 223682026-07-19T22:01:47Z2026-07-21T07:34:49Z