---
OA_place: publisher
OA_type: gold
_id: '22368'
abstract:
- lang: eng
  text: "We study simple dynamics in the population protocol model, in\r\nwhich \U0001D45B
    agents start with totally ordered initial opinions \U0001D4651, \U0001D4652, .
    . . ,\r\n\U0001D465\U0001D45B and, in each round, a randomly chosen agent changes
    its opinion\r\nas a function of the opinion of other randomly chosen agents. Such\r\ndynamics
    often converge to consensus on a single fixation value \U0001D44Bˆ.\r\nThis paper
    asks how to control the distribution of \U0001D44Bˆ as a randomised\r\nchoice
    among the initial opinions by designing suitable simple\r\ndynamics. Writing the
    sorted initial values as \U0001D465(1) ≤ · · · ≤ \U0001D465(\U0001D45B)\r\n,\r\nwe
    design two protocols that realise natural target laws over order\r\nstatistics.\r\nFirst,
    for a parameter \U0001D45D ∈ (0, 1), our geometric protocol biases\r\ntoward larger
    opinions and satisfies P\r\n\r\n\U0001D44Bˆ = \U0001D465(\U0001D458)\r\n\r\n∝
    \U0001D45D\r\n\U0001D45B−\U0001D458\r\n, for\r\n\U0001D458 = 1, . . . , \U0001D45B.
    Equivalently, P\r\n\r\n\U0001D44Bˆ = \U0001D465(\U0001D458)\r\n\r\n= (1 − \U0001D45D)\U0001D45D\r\n\U0001D45B−\U0001D458\r\n/(1
    − \U0001D45D\r\n\U0001D45B\r\n).\r\nSecond, our binomial protocol assigns a shifted
    binomial law to the\r\nranks in ascending order: if \U0001D43E −1 ∼ Bin(\U0001D45B−1,
    1−\U0001D45D), then \U0001D44Bˆ = \U0001D465(\U0001D43E)\r\n,\r\ni.e., P\r\n\r\n\U0001D44Bˆ
    = \U0001D465(\U0001D458)\r\n\r\n=\r\n\U0001D45B−1\r\n\U0001D458−1\r\n\x01\r\n\U0001D45D\r\n\U0001D45B−\U0001D458\r\n(1
    − \U0001D45D)\r\n\U0001D458−1\r\n, for \U0001D458 = 1, . . . , \U0001D45B.\r\nApplications
    of this include computing the Top-\U0001D458 values for\r\nsmall \U0001D458 on
    general interaction graphs. A central contribution of\r\nthis work is that, in
    contrast to most population protocols, we can\r\ncharacterise the fixation distribution
    in closed form. This is enabled\r\nby a novel analysis technique, which also yields
    applications: we\r\nderive new results for the Median protocol that extend the
    state of\r\nthe art."
acknowledgement: "This work has been supported by the AID INRIA-DGA project\r\nn°2023000872
  “BioSwarm”, the French government National Research Agency (ANR) through the UCA
  JEDI (ANR-15-IDEX-01),\r\nthe EUR DS4H (ANR-17-EURE-004) and the 3IA Cote d’Azur
  Investments ANR-23-IACL-0001, and EPSRC grant EP/W005573/1"
article_processing_charge: No
author:
- first_name: Niccolò
  full_name: D'Archivio, Niccolò
  last_name: D'Archivio
- first_name: Hind
  full_name: Almahmoud, Hind
  last_name: Almahmoud
- first_name: Emanuele
  full_name: Natale, Emanuele
  last_name: Natale
- first_name: Frederik
  full_name: Mallmann-Trenn, Frederik
  id: 68748c44-84d5-11f1-b4f6-ca083374e553
  last_name: Mallmann-Trenn
citation:
  ama: '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>'
  apa: '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>'
  chicago: 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>.
  ieee: 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.
  ista: '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.'
  mla: 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>.
  short: 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.
conference:
  end_date: 2026-07-10
  location: Egham, United Kingdom
  name: 'PODC: Symposium on Principles of Distributed Computing'
  start_date: 2026-07-06
corr_author: '1'
das_tickbox: '0'
date_created: 2026-07-19T22:01:47Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-21T07:34:49Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3796701.3815922
file:
- access_level: open_access
  checksum: e8208393a016d8e71d7b26c402045488
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-21T07:31:29Z
  date_updated: 2026-07-21T07:31:29Z
  file_id: '22379'
  file_name: 2026_ACMPODC_dArchivio.pdf
  file_size: 824239
  relation: main_file
  success: 1
file_date_updated: 2026-07-21T07:31:29Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 425-436
publication: Proceedings of the Annual ACM Symposium on Principles of Distributed
  Computing
publication_identifier:
  isbn:
  - '9798400725128'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
researchdata_availability: no
scopus_import: '1'
status: public
supplementarymaterial: no
title: Order statistics in population protocols via simple dynamics
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...