---
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: Proceedings of the Annual ACM Symposium on
Principles of Distributed Computing. Association for Computing Machinery;
2026:77-87. doi:10.1145/3796701.3815920'
apa: 'Cooper, C., Mallmann-Trenn, F., Radzik, T., Shimizu, N., & Shiraga, T.
(2026). Undecided state dynamics with many opinions. In Proceedings of the
Annual ACM Symposium on Principles of Distributed Computing (pp. 77–87). Egham,
United Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815920'
chicago: Cooper, Colin, Frederik Mallmann-Trenn, Tomasz Radzik, Nobutaka Shimizu,
and Takeharu Shiraga. “Undecided State Dynamics with Many Opinions.” In Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing, 77–87.
Association for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815920.
ieee: C. Cooper, F. Mallmann-Trenn, T. Radzik, N. Shimizu, and T. Shiraga, “Undecided
state dynamics with many opinions,” in Proceedings of the Annual ACM Symposium
on Principles of Distributed Computing, 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.” Proceedings
of the Annual ACM Symposium on Principles of Distributed Computing, Association
for Computing Machinery, 2026, pp. 77–87, doi:10.1145/3796701.3815920.
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'
...