---
OA_place: publisher
OA_type: hybrid
_id: '20051'
abstract:
- lang: eng
text: "We revisit the majority problem in the population protocol communication
model, as first studied by Angluin et al. (Distributed Computing 2008). We consider
a more general version of this problem known as plurality consensus, which has
already been studied intensively in the literature. In this problem, each node
in a system of n nodes, has initially one of k different opinions, and they need
to agree on the (relative) majority opinion. In particular, we consider the important
and intensively studied model of Undecided State Dynamics.\r\nOur main contribution
is an almost tight lower bound on the stabilization time: we prove that there
exists an initial configuration, even with bias \\Delta = \\omega(\\sqrt{n\\log
n}), where stabilization requires \\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})
interactions, or equivalently, \\Omega(k\\log \\frac {\\sqrt n} {k \\log n}) parallel
time for any k = o\\left(\\frac {\\sqrt n}{\\log n}\\right). This bound is tight
for any k \\le n^{\\frac 1 2 - \\epsilon}, where \\epsilon >0 can be any small
constant, as Amir et al.~(PODC'23) gave a O(k\\log n) parallel time upper bound
for k = O\\left(\\frac {\\sqrt n} {\\log ^2 n}\\right)."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the European Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/I5862,grant
DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with\r\nadditional funding from
the netidee SCIENCE Stiftung, 2020–2024\r\nand the German Research Foundation (DFG),
grant 470029389\r\n(FlexNets)."
article_processing_charge: Yes (via OA deal)
arxiv: 1
author:
- 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: Robert
full_name: Elsässer, Robert
last_name: Elsässer
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'El-Hayek A, Elsässer R, Schmid S. An almost tight lower bound for plurality
consensus with undecided state dynamics in the population protocol model. In:
Proceedings of the ACM Symposium on Principles of Distributed Computing.
Association for Computing Machinery; 2025. doi:10.1145/3732772.3733505'
apa: 'El-Hayek, A., Elsässer, R., & Schmid, S. (2025). An almost tight lower
bound for plurality consensus with undecided state dynamics in the population
protocol model. In Proceedings of the ACM Symposium on Principles of Distributed
Computing. Huatulco, Mexico: Association for Computing Machinery. https://doi.org/10.1145/3732772.3733505'
chicago: El-Hayek, Antoine, Robert Elsässer, and Stefan Schmid. “An Almost Tight
Lower Bound for Plurality Consensus with Undecided State Dynamics in the Population
Protocol Model.” In Proceedings of the ACM Symposium on Principles of Distributed
Computing. Association for Computing Machinery, 2025. https://doi.org/10.1145/3732772.3733505.
ieee: A. El-Hayek, R. Elsässer, and S. Schmid, “An almost tight lower bound for
plurality consensus with undecided state dynamics in the population protocol model,”
in Proceedings of the ACM Symposium on Principles of Distributed Computing,
Huatulco, Mexico, 2025.
ista: 'El-Hayek A, Elsässer R, Schmid S. 2025. An almost tight lower bound for plurality
consensus with undecided state dynamics in the population protocol model. Proceedings
of the ACM Symposium on Principles of Distributed Computing. PODC: Symposium on
Principles of Distributed Computing.'
mla: El-Hayek, Antoine, et al. “An Almost Tight Lower Bound for Plurality Consensus
with Undecided State Dynamics in the Population Protocol Model.” Proceedings
of the ACM Symposium on Principles of Distributed Computing, Association for
Computing Machinery, 2025, doi:10.1145/3732772.3733505.
short: A. El-Hayek, R. Elsässer, S. Schmid, in:, Proceedings of the ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery, 2025.
conference:
end_date: 2025-06-20
location: Huatulco, Mexico
name: 'PODC: Symposium on Principles of Distributed Computing'
start_date: 2025-06-16
corr_author: '1'
date_created: 2025-07-21T08:16:15Z
date_published: 2025-06-13T00:00:00Z
date_updated: 2025-10-16T13:08:45Z
day: '13'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3732772.3733505
ec_funded: 1
external_id:
arxiv:
- '2505.02765'
isi:
- '001525534800066'
file:
- access_level: open_access
checksum: 52976d226f3f691aa519d71c1c718fa5
content_type: application/pdf
creator: dernst
date_created: 2025-08-04T09:10:55Z
date_updated: 2025-08-04T09:10:55Z
file_id: '20115'
file_name: 2025_PODC_ElHayek.pdf
file_size: 2200347
relation: main_file
success: 1
file_date_updated: 2025-08-04T09:10:55Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
month: '06'
oa: 1
oa_version: Published Version
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
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- ' 9798400718854'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
status: public
title: An almost tight lower bound for plurality consensus with undecided state dynamics
in the population protocol model
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: '2025'
...