---
OA_place: publisher
OA_type: hybrid
_id: '20052'
abstract:
- lang: eng
text: "This paper revisits a fundamental distributed computing problem in the population
protocol model. Provided n agents each starting with an input color in [k], the
relative majority problem asks to find the predominant color. In the population
protocol model, at each time step, a scheduler selects two agents that first learn
each other's states and then update their states based on what they learned.\r\nWe
present the Circles protocol that solves the relative majority problem with k3
states. It is always-correct under weakly fair scheduling. Not only does it improve
upon the best known upper bound of O(k7), but it also shows a strikingly simpler
design inspired by energy minimization in chemical settings."
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/I5982,
and grant DOI 10.55776/P33775 with additional funding from the netidee SCIENCE Stiftung,
2020–2024 and the German Research Foundation (DFG), grant 470029389 (FlexNets). '
article_processing_charge: No
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. Brief announcement: Minimizing
energy solves relative majority with a cubic number of states in population protocols.
In: Proceedings of the ACM Symposium on Principles of Distributed Computing.
Association for Computing Machinery; 2025:549-552. doi:10.1145/3732772.3733512'
apa: 'Breitkopf, T.-L., Dallot, J., El-Hayek, A., & Schmid, S. (2025). Brief
announcement: Minimizing energy solves relative majority with a cubic number of
states in population protocols. In Proceedings of the ACM Symposium on Principles
of Distributed Computing (pp. 549–552). Huatulco, Mexico: Association for
Computing Machinery. https://doi.org/10.1145/3732772.3733512'
chicago: 'Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid.
“Brief Announcement: Minimizing Energy Solves Relative Majority with a Cubic Number
of States in Population Protocols.” In Proceedings of the ACM Symposium on
Principles of Distributed Computing, 549–52. Association for Computing Machinery,
2025. https://doi.org/10.1145/3732772.3733512.'
ieee: 'T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Brief announcement:
Minimizing energy solves relative majority with a cubic number of states in population
protocols,” in Proceedings of the ACM Symposium on Principles of Distributed
Computing, Huatulco, Mexico, 2025, pp. 549–552.'
ista: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2025. Brief announcement:
Minimizing energy solves relative majority with a cubic number of states in population
protocols. Proceedings of the ACM Symposium on Principles of Distributed Computing.
PODC: Symposium on Principles of Distributed Computing, 549–552.'
mla: 'Breitkopf, Tom-Lukas, et al. “Brief Announcement: Minimizing Energy Solves
Relative Majority with a Cubic Number of States in Population Protocols.” Proceedings
of the ACM Symposium on Principles of Distributed Computing, Association for
Computing Machinery, 2025, pp. 549–52, doi:10.1145/3732772.3733512.'
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, 2025, pp. 549–552.
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:17:04Z
date_published: 2025-06-13T00:00:00Z
date_updated: 2026-02-16T11:46:37Z
day: '13'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.1145/3732772.3733512
ec_funded: 1
external_id:
isi:
- '001525534800069'
file:
- access_level: open_access
checksum: e99679ffb28877b7cea4d54860302790
content_type: application/pdf
creator: dernst
date_created: 2025-08-05T07:32:01Z
date_updated: 2025-08-05T07:32:01Z
file_id: '20123'
file_name: 2025_PODC_Breitkopf.pdf
file_size: 549706
relation: main_file
success: 1
file_date_updated: 2025-08-05T07:32:01Z
has_accepted_license: '1'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
month: '06'
oa: 1
oa_version: Published Version
page: 549-552
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: 'Brief announcement: Minimizing energy solves relative majority with a cubic
number of 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: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...