---
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
fulldoi: https://doi.org/10.1145/3732772.3733512
has_accepted_license: '1'
isi: 1
language:
- iso: eng
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'
...
---
OA_place: publisher
OA_type: hybrid
_id: '20053'
abstract:
- lang: eng
text: "Liquid democracy is a transitive vote delegation mechanism over voting graphs.
It enables each voter to delegate their vote(s) to another better-informed voter,
with the goal of collectively making a better decision. The question of whether
liquid democracy outperforms direct voting has been previously studied in the
context of local delegation mechanisms (where voters can only delegate to someone
in their neighbourhood) and binary decision problems. It has previously been shown
that it is impossible for local delegation mechanisms to outperform direct voting
in general graphs. This raises the question: for which classes of graphs do local
delegation mechanisms yield good results?\r\nIn this work, we analyse (1) properties
of specific graphs and (2) properties of local delegation mechanisms on these
graphs, determining where local delegation actually outperforms direct voting.
We show that a critical graph property enabling liquid democracy is that the voting
outcome of local delegation mechanisms preserves a sufficient amount of variance,
thereby avoiding situations where delegation falls behind direct voting1. These
insights allow us to prove our main results, namely that there exist local delegation
mechanisms that perform no worse and in fact quantitatively better than direct
voting in natural graph topologies like complete, random d-regular, and bounded
degree graphs, lending a more nuanced perspective to previous impossibility results."
acknowledgement: This work was partially supported by MOE-T2EP20122-0014 (DataDriven
Distributed Algorithms), German Research Foundation (DFG) project ReNO (SPP 2378)
from 2023-2027, ERC CoG 863818 (ForMSMArt) and Austrian Science Fund (FWF) 10.55776/COE12.
article_processing_charge: No
author:
- first_name: Krishnendu
full_name: Chatterjee, Krishnendu
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
- first_name: Seth
full_name: Gilbert, Seth
last_name: Gilbert
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
- first_name: Jakub
full_name: Svoboda, Jakub
id: 130759D2-D7DD-11E9-87D2-DE0DE6697425
last_name: Svoboda
orcid: 0000-0002-1419-3267
- first_name: Michelle X
full_name: Yeo, Michelle X
id: 2D82B818-F248-11E8-B48F-1D18A9856A87
last_name: Yeo
orcid: 0009-0001-3676-4809
citation:
ama: 'Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. When is liquid democracy
possible?: On the manipulation of variance. In: Proceedings of the ACM Symposium
on Principles of Distributed Computing. Association for Computing Machinery;
2025:241-251. doi:10.1145/3732772.3733544'
apa: 'Chatterjee, K., Gilbert, S., Schmid, S., Svoboda, J., & Yeo, M. X. (2025).
When is liquid democracy possible?: On the manipulation of variance. In Proceedings
of the ACM Symposium on Principles of Distributed Computing (pp. 241–251).
Huatulco, Mexico: Association for Computing Machinery. https://doi.org/10.1145/3732772.3733544'
chicago: 'Chatterjee, Krishnendu, Seth Gilbert, Stefan Schmid, Jakub Svoboda, and
Michelle X Yeo. “When Is Liquid Democracy Possible?: On the Manipulation of Variance.”
In Proceedings of the ACM Symposium on Principles of Distributed Computing,
241–51. Association for Computing Machinery, 2025. https://doi.org/10.1145/3732772.3733544.'
ieee: 'K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, and M. X. Yeo, “When is
liquid democracy possible?: On the manipulation of variance,” in Proceedings
of the ACM Symposium on Principles of Distributed Computing, Huatulco, Mexico,
2025, pp. 241–251.'
ista: 'Chatterjee K, Gilbert S, Schmid S, Svoboda J, Yeo MX. 2025. When is liquid
democracy possible?: On the manipulation of variance. Proceedings of the ACM Symposium
on Principles of Distributed Computing. PODC: Symposium on Principles of Distributed
Computing, 241–251.'
mla: 'Chatterjee, Krishnendu, et al. “When Is Liquid Democracy Possible?: On the
Manipulation of Variance.” Proceedings of the ACM Symposium on Principles of
Distributed Computing, Association for Computing Machinery, 2025, pp. 241–51,
doi:10.1145/3732772.3733544.'
short: K. Chatterjee, S. Gilbert, S. Schmid, J. Svoboda, M.X. Yeo, in:, Proceedings
of the ACM Symposium on Principles of Distributed Computing, Association for Computing
Machinery, 2025, pp. 241–251.
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:18:26Z
date_published: 2025-06-13T00:00:00Z
date_updated: 2026-02-16T11:46:51Z
day: '13'
ddc:
- '000'
department:
- _id: KrCh
- _id: KrPi
doi: 10.1145/3732772.3733544
ec_funded: 1
external_id:
isi:
- '001525534800030'
file:
- access_level: open_access
checksum: cd628fe54d96e9fc6cc789bb8145422b
content_type: application/pdf
creator: dernst
date_created: 2025-08-05T07:15:31Z
date_updated: 2025-08-05T07:15:31Z
file_id: '20122'
file_name: 2025_PODC_Chatterjee.pdf
file_size: 783297
relation: main_file
success: 1
file_date_updated: 2025-08-05T07:15:31Z
fulldoi: https://doi.org/10.1145/3732772.3733544
has_accepted_license: '1'
isi: 1
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://eprint.iacr.org/2025/745
month: '06'
oa: 1
oa_version: Published Version
page: 241-251
project:
- _id: 0599E47C-7A3F-11EA-A408-12923DDC885E
call_identifier: H2020
grant_number: '863818'
name: 'Formal Methods for Stochastic Models: Algorithms and Applications'
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: 'When is liquid democracy possible?: On the manipulation of variance'
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'
...