---
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'
...
---
OA_place: publisher
OA_type: gold
_id: '22367'
abstract:
- lang: eng
  text: "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 \r\nk\r\n=\r\nO\r\n(\r\nn\r\n/\r\n(\r\nlog\r\n⁡\r\nn\r\n)\r\n2\r\n)\r\n
    (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.\r\nIn 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
    \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\n,\r\nn\r\n}\r\n)\r\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 \r\nO\r\n~\r\n(\r\nmin\r\n{\r\nk\r\nn\r\n,\r\nn\r\n3\r\n/\r\n2\r\n}\r\n)\r\n
    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."
acknowledgement: "Nobutaka Shimizu is supported by JSPS KAKENHI Grant Number\r\n23K16837.
  Takeharu Shiraga is supported by JSPS KAKENHI Grant\r\nNumber 23K16840, and JST
  CRONOS Grant Number JPMJCS24K2.\r\nColin Cooper is supported by a Mercator Fellowship
  from DFG\r\nProject 491453517 at the University of Hamburg. We thank the\r\nanonymous
  reviewers for their helpful comments and suggestions."
article_processing_charge: No
arxiv: 1
author:
- first_name: Colin
  full_name: Cooper, Colin
  last_name: Cooper
- first_name: Frederik
  full_name: Mallmann-Trenn, Frederik
  id: 68748c44-84d5-11f1-b4f6-ca083374e553
  last_name: Mallmann-Trenn
- first_name: Tomasz
  full_name: Radzik, Tomasz
  last_name: Radzik
- first_name: Nobutaka
  full_name: Shimizu, Nobutaka
  last_name: Shimizu
- first_name: Takeharu
  full_name: Shiraga, Takeharu
  last_name: Shiraga
citation:
  ama: 'Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. Undecided state
    dynamics with many opinions. In: <i>Proceedings of the Annual ACM Symposium on
    Principles of Distributed Computing</i>. Association for Computing Machinery;
    2026:77-87. doi:<a href="https://doi.org/10.1145/3796701.3815920">10.1145/3796701.3815920</a>'
  apa: 'Cooper, C., Mallmann-Trenn, F., Radzik, T., Shimizu, N., &#38; Shiraga, T.
    (2026). Undecided state dynamics with many opinions. In <i>Proceedings of the
    Annual ACM Symposium on Principles of Distributed Computing</i> (pp. 77–87). Egham,
    United Kingdom: Association for Computing Machinery. <a href="https://doi.org/10.1145/3796701.3815920">https://doi.org/10.1145/3796701.3815920</a>'
  chicago: Cooper, Colin, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu,
    and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions.” In <i>Proceedings
    of the Annual ACM Symposium on Principles of Distributed Computing</i>, 77–87.
    Association for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3796701.3815920">https://doi.org/10.1145/3796701.3815920</a>.
  ieee: C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga, “Undecided
    state dynamics with many opinions,” in <i>Proceedings of the Annual ACM Symposium
    on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 77–87.
  ista: 'Cooper C, Mallmann-Trenn F, Radzik T, Shimizu N, Shiraga T. 2026. Undecided
    state dynamics with many opinions. Proceedings of the Annual ACM Symposium on
    Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
    Computing, 77–87.'
  mla: Cooper, Colin, et al. “Undecided State Dynamics with Many Opinions.” <i>Proceedings
    of the Annual ACM Symposium on Principles of Distributed Computing</i>, Association
    for Computing Machinery, 2026, pp. 77–87, doi:<a href="https://doi.org/10.1145/3796701.3815920">10.1145/3796701.3815920</a>.
  short: C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, T. Shiraga, in:, Proceedings
    of the Annual ACM Symposium on Principles of Distributed Computing, Association
    for Computing Machinery, 2026, pp. 77–87.
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: '1'
date_created: 2026-07-19T22:01:47Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-21T07:54:01Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3796701.3815920
external_id:
  arxiv:
  - '2603.02636'
file:
- access_level: open_access
  checksum: 9ada61feba1e93fd72867a5ba4ee8bb8
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-21T07:51:58Z
  date_updated: 2026-07-21T07:51:58Z
  file_id: '22380'
  file_name: 2026_ACMPODC_Cooper.pdf
  file_size: 709077
  relation: main_file
  success: 1
file_date_updated: 2026-07-21T07:51:58Z
has_accepted_license: '1'
keyword:
- consensus dynamics
- undecided state dynamics
- gossip model
- population protocol model
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 77-87
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: Undecided state dynamics with many opinions
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'
...
---
OA_place: publisher
OA_type: gold
_id: '22327'
abstract:
- lang: eng
  text: "Population protocols are a model of distributed computing where\r\n\U0001D45B
    agents, each a simple finite-state machine, interact in pairs to\r\nsolve a common
    task against a (adversarial) interaction scheduler.\r\nThis model was intensively
    studied in recent years; in particular,\r\nthe problem of relative majority received
    much attention: Each\r\nagent starts with an input opinion (or color) out of \U0001D458
    possibilities,\r\nand the goal is for each agent to eventually output the color
    with\r\nthe largest support in the population. Before our work, the state\r\ncomplexity
    (the minimum number of states required per agent) was\r\nonly known to be between
    Ω(\U0001D458\r\n2\r\n) and\U0001D442(\U0001D458\r\n7\r\n). Our main contribution\r\nis
    a population protocol that solves the relative majority problem\r\nwith \U0001D458\r\n3\r\nstates.
    We achieve this result with a new protocol called\r\nCircles. While prior approaches
    in the literature relied on duels of\r\nagents to find the majority color — an
    approach that proved effective\r\nfor the case with two colors — Circles partitions
    the agents into\r\ncircular linked lists of decreasing sizes, with the property
    that no\r\ntwo agents with the same initial color lie in the same circle. We\r\nshow
    that Circles always correctly computes the desired structure\r\nagainst the most
    adversarial of schedulers (weakly fair). We then\r\nshow that a trivial extension
    of Circles solves the relative majority\r\nproblem. We extend our protocol to
    handle various tie-breaking\r\nmechanisms or to support the case where the agents
    do not share a\r\nprior ordering of the colors. Finally, we show that a modification
    of\r\nCircles solves the ranking problem with 2 · \U0001D458^4\r\nstates, where
    each\r\nagent must output the rank of its initial color in the population."
acknowledgement: "Funded by the European union. Views and opinions expressed are\r\nhowever
  those of the author(s) only and do not necessarily reflect\r\nthose of the European
  Union or the European Research Council\r\nExecutive Agency. Neither the European
  Union nor the granting authority can be held responsible for them. This project
  has received\r\nfunding from the European Research Council (ERC) under the European
  Union’s Horizon 2020 research and innovation programme\r\n(MoDynStruct, No. 101019564)
  and the Austrian Science\r\nFund (FWF) grant DOI 10.55776/I5982. For open access
  purposes,\r\nthe author has applied a CC BY public copyright license to any\r\nauthor-accepted
  manuscript version arising from this submission."
article_processing_charge: Yes
arxiv: 1
author:
- first_name: Tom-Lukas
  full_name: Breitkopf, Tom-Lukas
  last_name: Breitkopf
- first_name: Julien
  full_name: Dallot, Julien
  last_name: Dallot
- first_name: Antoine
  full_name: El-Hayek, Antoine
  id: 888a098e-fcac-11ee-aff7-d347be57b725
  last_name: El-Hayek
  orcid: 0000-0003-4268-7368
- first_name: Stefan
  full_name: Schmid, Stefan
  last_name: Schmid
citation:
  ama: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. Ranking opinions with few states
    in population protocols. In: <i>Proceedings of the ACM Symposium on Principles
    of Distributed Computing</i>. Association for Computing Machinery; 2026:414-424.
    doi:<a href="https://doi.org/10.1145/3796701.3815913">10.1145/3796701.3815913</a>'
  apa: 'Breitkopf, T.-L., Dallot, J., El-Hayek, A., &#38; Schmid, S. (2026). Ranking
    opinions with few states in population protocols. In <i>Proceedings of the ACM
    Symposium on Principles of Distributed Computing</i> (pp. 414–424). Egham, United
    Kingdom: Association for Computing Machinery. <a href="https://doi.org/10.1145/3796701.3815913">https://doi.org/10.1145/3796701.3815913</a>'
  chicago: Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid.
    “Ranking Opinions with Few States in Population Protocols.” In <i>Proceedings
    of the ACM Symposium on Principles of Distributed Computing</i>, 414–24. Association
    for Computing Machinery, 2026. <a href="https://doi.org/10.1145/3796701.3815913">https://doi.org/10.1145/3796701.3815913</a>.
  ieee: T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Ranking opinions
    with few states in population protocols,” in <i>Proceedings of the ACM Symposium
    on Principles of Distributed Computing</i>, Egham, United Kingdom, 2026, pp. 414–424.
  ista: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2026. Ranking opinions with
    few states in population protocols. Proceedings of the ACM Symposium on Principles
    of Distributed Computing. PODC: Symposium on Principles of Distributed Computing,
    414–424.'
  mla: Breitkopf, Tom-Lukas, et al. “Ranking Opinions with Few States in Population
    Protocols.” <i>Proceedings of the ACM Symposium on Principles of Distributed Computing</i>,
    Association for Computing Machinery, 2026, pp. 414–24, doi:<a href="https://doi.org/10.1145/3796701.3815913">10.1145/3796701.3815913</a>.
  short: T.-L. Breitkopf, J. Dallot, A. El-Hayek, S. Schmid, in:, Proceedings of the
    ACM Symposium on Principles of Distributed Computing, Association for Computing
    Machinery, 2026, pp. 414–424.
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-14T05:40:17Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-22T07:49:22Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1145/3796701.3815913
ec_funded: 1
external_id:
  arxiv:
  - '2605.18707'
file:
- access_level: open_access
  checksum: e56da70c1b2e7e663d2d8106cf07a30a
  content_type: application/pdf
  creator: dernst
  date_created: 2026-07-16T11:18:44Z
  date_updated: 2026-07-16T11:18:44Z
  file_id: '22353'
  file_name: 2026_ACMPODC_Breitkopf.pdf
  file_size: 702140
  relation: main_file
  success: 1
file_date_updated: 2026-07-16T11:18:44Z
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 414 - 424
project:
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
  call_identifier: H2020
  grant_number: '101019564'
  name: The design and evaluation of modern fully dynamic data structures
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
  grant_number: I05982
  name: Static and Dynamic Hierarchical Graph Decompositions
publication: Proceedings of the 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: Ranking opinions with few states in population protocols
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...