---
OA_place: repository
OA_type: green
_id: '21720'
abstract:
- lang: eng
text: "We present an exact fully-dynamic minimum cut algorithm that runs in \U0001D45B\U0001D45C(1)
deterministic update time when the minimum cut size is at most 2Θ(log3/4−\U0001D450\U0001D45B)
for any \U0001D450 >0, improving on the previous algorithm of Jin, Sun, and Thorup
(SODA 2024) whose minimum cut size limit is (log\U0001D45B)\U0001D45C(1). Combined
with graph sparsification, we obtain the first (1 +\U0001D716)-approximate fully-dynamic
minimum cut algorithm on weighted graphs, for any \U0001D716 ≥2−Θ(log3/4−\U0001D450\U0001D45B),
in \U0001D45B\U0001D45C(1) randomized update time.\r\nOur main technical contribution
is a deterministic local minimum cut algorithm, which replaces the randomized
LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025)."
acknowledgement: Funded by the European union. Views and opinions expressed are however
those of the author(s) only and do not necessarily reflect those of the European
Union or the European Research Council Executive Agency. Neither the European Union
nor the granting authority can be held responsible for them. 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. For open access purposes, the author
has applied a CC BY public copyright license to any author-accepted manuscript version
arising from this submission.
article_processing_charge: No
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Jason
full_name: Li, Jason
last_name: Li
citation:
ama: 'El-Hayek A, Henzinger M, Li J. Deterministic and exact fully-dynamic minimum
cut of superpolylogarithmic size in subpolynomial time. In: Proceedings of
the Annual ACM SIAM Symposium on Discrete Algorithms. Vol 2026. Society for
Industrial and Applied Mathematics; 2026:613-663. doi:10.1137/1.9781611978971.25'
apa: 'El-Hayek, A., Henzinger, M., & Li, J. (2026). Deterministic and exact
fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time.
In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms
(Vol. 2026, pp. 613–663). Vancouver, Canada: Society for Industrial and Applied
Mathematics. https://doi.org/10.1137/1.9781611978971.25'
chicago: El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Deterministic and Exact
Fully-Dynamic Minimum Cut of Superpolylogarithmic Size in Subpolynomial Time.”
In Proceedings of the Annual ACM SIAM Symposium on Discrete Algorithms,
2026:613–63. Society for Industrial and Applied Mathematics, 2026. https://doi.org/10.1137/1.9781611978971.25.
ieee: A. El-Hayek, M. Henzinger, and J. Li, “Deterministic and exact fully-dynamic
minimum cut of superpolylogarithmic size in subpolynomial time,” in Proceedings
of the Annual ACM SIAM Symposium on Discrete Algorithms, Vancouver, Canada,
2026, vol. 2026, pp. 613–663.
ista: 'El-Hayek A, Henzinger M, Li J. 2026. Deterministic and exact fully-dynamic
minimum cut of superpolylogarithmic size in subpolynomial time. Proceedings of
the Annual ACM SIAM Symposium on Discrete Algorithms. SODA: Symposium on Discrete
Algorithms vol. 2026, 613–663.'
mla: El-Hayek, Antoine, et al. “Deterministic and Exact Fully-Dynamic Minimum Cut
of Superpolylogarithmic Size in Subpolynomial Time.” Proceedings of the Annual
ACM SIAM Symposium on Discrete Algorithms, vol. 2026, Society for Industrial
and Applied Mathematics, 2026, pp. 613–63, doi:10.1137/1.9781611978971.25.
short: A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the Annual ACM SIAM
Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
2026, pp. 613–663.
conference:
end_date: 2026-01-14
location: Vancouver, Canada
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2026-01-11
date_created: 2026-04-12T22:01:51Z
date_published: 2026-01-07T00:00:00Z
date_updated: 2026-05-04T11:36:47Z
day: '07'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1137/1.9781611978971.25
ec_funded: 1
external_id:
arxiv:
- '2512.13105'
intvolume: ' 2026'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2512.13105
month: '01'
oa: 1
oa_version: Preprint
page: 613-663
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 Annual ACM SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611978971'
eissn:
- 1557-9468
issn:
- 1071-9040
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size
in subpolynomial time
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 2026
year: '2026'
...
---
OA_place: publisher
OA_type: gold
_id: '19858'
abstract:
- lang: eng
text: "Given a graph G that undergoes a sequence of edge insertions and deletions,
we study the Maximum k-Edge Coloring problem (MkEC): Having access to k different
colors, color as many edges of G as possible such that no two adjacent edges share
the same color. While this problem is different from simply maintaining a b-matching
with b = k, the two problems are related. However, maximum b-matching can be solved
efficiently in the static setting, whereas MkEC is NP-hard and even APX-hard for
k ≥ 2. \r\nWe present new results on both problems: For b-matching, we show a
new integrality gap result and we adapt Wajc’s matching sparsification scheme
[David Wajc, 2020] for the case where b is a constant.\r\nUsing these as basis,
we give three new algorithms for the dynamic MkEC problem: Our MatchO algorithm
builds on the dynamic (2+ε)-approximation algorithm of Bhattacharya, Gupta, and
Mohan [Sayan Bhattacharya et al., 2017] for b-matching and achieves a (2+ε)(k+1)/k-approximation
in O(poly(log n, ε^-1)) update time against an oblivious adversary. Our MatchA
algorithm builds on the dynamic (7+ε)-approximation algorithm by Bhattacharya,
Henzinger, and Italiano [Sayan Bhattacharya et al., 2015] for fractional b-matching
and achieves a (7+ε)(3k+3)/(3k-1)-approximation in O(poly(log n, ε^-1)) update
time against an adaptive adversary. Moreover, our reductions use the dynamic b-matching
algorithm as a black box, so any future improvement in the approximation ratio
for dynamic b-matching will automatically translate into a better approximation
ratio for our algorithms. Finally, we present a greedy algorithm with O(Δ+k) update
time, which guarantees a 2.16 approximation factor."
acknowledgement: "This project has received funding from the European Research Council
(ERC) under the\r\nEuropean Union’s Horizon 2020 research and innovation programme
(MoDynStruct, No. 101019564) and the Austrian Science Fund (FWF) grant DOI 10.55776/Z422,
grant DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding
from the netidee SCIENCE Stiftung, 2020–2024. This work was further supported by
the Federal Ministry of Education and Research (BMBF) project, 6G-RIC: 6G Research
and Innovation Cluster, grant 16KISK020K."
alternative_title:
- LIPIcs
article_number: '4'
article_processing_charge: No
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: Kathrin
full_name: Hanauer, Kathrin
last_name: Hanauer
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
citation:
ama: 'El-Hayek A, Hanauer K, Henzinger M. On b-matching and fully-dynamic maximum
k-edge coloring. In: 4th Symposium on Algorithmic Foundations of Dynamic Networks.
Vol 330. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2025. doi:10.4230/LIPIcs.SAND.2025.4'
apa: 'El-Hayek, A., Hanauer, K., & Henzinger, M. (2025). On b-matching and fully-dynamic
maximum k-edge coloring. In 4th Symposium on Algorithmic Foundations of Dynamic
Networks (Vol. 330). Liverpool, United Kingdom: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPIcs.SAND.2025.4'
chicago: El-Hayek, Antoine, Kathrin Hanauer, and Monika Henzinger. “On B-Matching
and Fully-Dynamic Maximum k-Edge Coloring.” In 4th Symposium on Algorithmic
Foundations of Dynamic Networks, Vol. 330. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2025. https://doi.org/10.4230/LIPIcs.SAND.2025.4.
ieee: A. El-Hayek, K. Hanauer, and M. Henzinger, “On b-matching and fully-dynamic
maximum k-edge coloring,” in 4th Symposium on Algorithmic Foundations of Dynamic
Networks, Liverpool, United Kingdom, 2025, vol. 330.
ista: 'El-Hayek A, Hanauer K, Henzinger M. 2025. On b-matching and fully-dynamic
maximum k-edge coloring. 4th Symposium on Algorithmic Foundations of Dynamic Networks.
SAND: Symposium on Algorithmic Foundations of Dynamic Networks, LIPIcs, vol. 330,
4.'
mla: El-Hayek, Antoine, et al. “On B-Matching and Fully-Dynamic Maximum k-Edge Coloring.”
4th Symposium on Algorithmic Foundations of Dynamic Networks, vol. 330,
4, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, doi:10.4230/LIPIcs.SAND.2025.4.
short: A. El-Hayek, K. Hanauer, M. Henzinger, in:, 4th Symposium on Algorithmic
Foundations of Dynamic Networks, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2025.
conference:
end_date: 2025-06-11
location: Liverpool, United Kingdom
name: 'SAND: Symposium on Algorithmic Foundations of Dynamic Networks'
start_date: 2025-06-09
corr_author: '1'
date_created: 2025-06-22T22:02:06Z
date_published: 2025-06-02T00:00:00Z
date_updated: 2025-09-30T13:37:28Z
day: '02'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.SAND.2025.4
ec_funded: 1
external_id:
arxiv:
- '2310.01149'
isi:
- '001532136900004'
file:
- access_level: open_access
checksum: ad93a1e052adb29d7bfe8bd551bab193
content_type: application/pdf
creator: dernst
date_created: 2025-06-23T11:23:29Z
date_updated: 2025-06-23T11:23:29Z
file_id: '19872'
file_name: 2025_LIPIcs_ElHayek.pdf
file_size: 995666
relation: main_file
success: 1
file_date_updated: 2025-06-23T11:23:29Z
has_accepted_license: '1'
intvolume: ' 330'
isi: 1
language:
- iso: eng
license: https://creativecommons.org/licenses/by/4.0/
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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: 4th Symposium on Algorithmic Foundations of Dynamic Networks
publication_identifier:
isbn:
- '9783959773683'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: On b-matching and fully-dynamic maximum k-edge coloring
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: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 330
year: '2025'
...
---
OA_place: repository
OA_type: green
_id: '19982'
abstract:
- lang: eng
text: "Dynamically maintaining the minimum cut in a graph G under edge insertions
and deletion is a fundamental problem in dynamic graph algorithms for which no
conditional lower bound on the time per operation exists. In an n-node graph the
best known (1 + o (1))-approximate algorithm takes update time [14]. If the minimum
cut is guaranteed to be (log n )o (1), a deterministic exact algorithm with n
o (1) update time exists [8].\r\nWe present the first fully dynamic algorithm
for (1 + o (1))-approximate minimum cut with n o(1) update time. Our main technical
contribution is to show that it suffices to consider small-volume cuts in suitably
contracted graphs."
acknowledgement: This project has received funding from the European Research Council
(ERC) under the European Union’sHorizon 2020 research and innovation programme (MoDynStruct,
No. 101019564) and the Austrian Science Fund(FWF) grant DOI 10.55776/Z422, grant
DOI 10.55776/I5982, and grant DOI 10.55776/P33775 with additional funding from the
netidee SCIENCE Stiftung, 2020–2024.
article_processing_charge: No
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Jason
full_name: Li, Jason
last_name: Li
citation:
ama: 'El-Hayek A, Henzinger M, Li J. Fully dynamic approximate minimum cut in subpolynomial
time per operation. In: Proceedings of the 2025 Annual ACM-SIAM Symposium on
Discrete Algorithms. Society for Industrial and Applied Mathematics; 2025:750-784.
doi:10.1137/1.9781611978322.22'
apa: 'El-Hayek, A., Henzinger, M., & Li, J. (2025). Fully dynamic approximate
minimum cut in subpolynomial time per operation. In Proceedings of the 2025
Annual ACM-SIAM Symposium on Discrete Algorithms (pp. 750–784). New Orleans,
LA, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/1.9781611978322.22'
chicago: El-Hayek, Antoine, Monika Henzinger, and Jason Li. “Fully Dynamic Approximate
Minimum Cut in Subpolynomial Time per Operation.” In Proceedings of the 2025
Annual ACM-SIAM Symposium on Discrete Algorithms, 750–84. Society for Industrial
and Applied Mathematics, 2025. https://doi.org/10.1137/1.9781611978322.22.
ieee: A. El-Hayek, M. Henzinger, and J. Li, “Fully dynamic approximate minimum cut
in subpolynomial time per operation,” in Proceedings of the 2025 Annual ACM-SIAM
Symposium on Discrete Algorithms, New Orleans, LA, United States, 2025, pp.
750–784.
ista: 'El-Hayek A, Henzinger M, Li J. 2025. Fully dynamic approximate minimum cut
in subpolynomial time per operation. Proceedings of the 2025 Annual ACM-SIAM Symposium
on Discrete Algorithms. SODA: Symposium on Discrete Algorithms, 750–784.'
mla: El-Hayek, Antoine, et al. “Fully Dynamic Approximate Minimum Cut in Subpolynomial
Time per Operation.” Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete
Algorithms, Society for Industrial and Applied Mathematics, 2025, pp. 750–84,
doi:10.1137/1.9781611978322.22.
short: A. El-Hayek, M. Henzinger, J. Li, in:, Proceedings of the 2025 Annual ACM-SIAM
Symposium on Discrete Algorithms, Society for Industrial and Applied Mathematics,
2025, pp. 750–784.
conference:
end_date: 2025-01-15
location: New Orleans, LA, United States
name: 'SODA: Symposium on Discrete Algorithms'
start_date: 2025-01-12
corr_author: '1'
date_created: 2025-07-10T13:08:57Z
date_published: 2025-01-07T00:00:00Z
date_updated: 2025-12-29T12:30:04Z
day: '07'
department:
- _id: MoHe
doi: 10.1137/1.9781611978322.22
ec_funded: 1
external_id:
arxiv:
- '2412.15069'
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.48550/arXiv.2412.15069
month: '01'
oa: 1
oa_version: Preprint
page: 750-784
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: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _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 2025 Annual ACM-SIAM Symposium on Discrete Algorithms
publication_identifier:
eisbn:
- '9781611978322'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
status: public
title: Fully dynamic approximate minimum cut in subpolynomial time per operation
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2025'
...
---
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'
...
---
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
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: gold
_id: '18557'
abstract:
- lang: eng
text: Broadcast and Consensus are most fundamental tasks in distributed computing.
These tasks are particularly challenging in dynamic networks where communication
across the network links may be unreliable, e.g., due to mobility or failures.
Over the last years, researchers have derived several impossibility results and
high time complexity lower bounds for these tasks. Specifically for the setting
where in each round of communication the adversary is allowed to choose one rooted
tree along which the information is disseminated, there is a lower as well as
an upper bound that is linear in the number n of nodes for Broadcast and for n
≥ 3 the adversary can guarantee that Consensus never happens. This setting is
called the oblivious message adversary for rooted trees. Also note that if the
adversary is allowed to choose a graph that does not contain a rooted tree, then
it can guarantee that Broadcast and Consensus will never happen. However, such
deterministic adversarial models may be overly pessimistic, as many processes
in real-world settings are stochastic in nature rather than worst-case. This paper
studies Broadcast on stochastic dynamic networks and shows that the situation
is very different to the deterministic case. In particular, we show that if information
dissemination occurs along random rooted trees and directed Erdős–Rényi graphs,
Broadcast completes in O(log n) rounds of communication with high probability.
The fundamental insight in our analysis is that key variables are mutually independent.
We then study two adversarial models, (a) one with Byzantine nodes and (b) one
where an adversary controls the edges. (a) Our techniques without Byzantine nodes
are general enough so that they can be extended to Byzantine nodes. (b) In the
spirit of smoothed analysis, we introduce the notion of randomized oblivious message
adversary, where in each round, an adversary picks k ≤ 2n/3 edges to appear in
the communication network, and then a graph (e.g. rooted tree or directed Erdős–Rényi
graph) is chosen uniformly at random among the set of all such graphs that include
these edges. We show that Broadcast completes in a finite number of rounds, which
is, e.g., O(k+log n) rounds in rooted trees. We then extend these results to All-to-All
Broadcast, and Consensus, and give lower bounds that show that most of our upper
bounds are tight.
acknowledgement: "Antoine El-Hayek: This project has received funding from the Austrian
Science Fund\r\n(FWF) grant DOI 10.55776/P33775 with additional funding from the
netidee SCIENCE Stiftung,\r\n2020–2024.\r\nMonika Henzinger: This project has received
funding from the European Research Council (ERC)\r\nunder the European Union’s Horizon
2020 research and innovation programme (MoDynStruct,\r\nNo. 101019564) and the Austrian
Science Fund (FWF) grant DOI 10.55776/Z422, grant DOI\r\n10.55776/I5982, and grant
DOI 10.55776/P33775 with additional funding from the netidee SCIENCE\r\nStiftung,
2020–2024.\r\nStefan Schmid: This project has received funding from the German Research
Foundation (DFG),\r\nSPP 2378 (project ReNO), 2023-2027."
alternative_title:
- LIPIcs
article_number: '21'
article_processing_charge: Yes
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: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
- first_name: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Broadcast and Consensus in stochastic dynamic
networks with Byzantine nodes and adversarial edges. In: 38th International
Symposium on Distributed Computing. Vol 319. Schloss Dagstuhl - Leibniz-Zentrum
für Informatik; 2024. doi:10.4230/LIPIcs.DISC.2024.21'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2024). Broadcast and Consensus
in stochastic dynamic networks with Byzantine nodes and adversarial edges. In
38th International Symposium on Distributed Computing (Vol. 319). Madrid,
Spain: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.DISC.2024.21'
chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Broadcast and
Consensus in Stochastic Dynamic Networks with Byzantine Nodes and Adversarial
Edges.” In 38th International Symposium on Distributed Computing, Vol.
319. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024. https://doi.org/10.4230/LIPIcs.DISC.2024.21.
ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges,” in 38th International
Symposium on Distributed Computing, Madrid, Spain, 2024, vol. 319.
ista: 'El-Hayek A, Henzinger M, Schmid S. 2024. Broadcast and Consensus in stochastic
dynamic networks with Byzantine nodes and adversarial edges. 38th International
Symposium on Distributed Computing. DISC: Symposium on Distributed Computing,
LIPIcs, vol. 319, 21.'
mla: El-Hayek, Antoine, et al. “Broadcast and Consensus in Stochastic Dynamic Networks
with Byzantine Nodes and Adversarial Edges.” 38th International Symposium on
Distributed Computing, vol. 319, 21, Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2024, doi:10.4230/LIPIcs.DISC.2024.21.
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, 38th International Symposium on
Distributed Computing, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2024.
conference:
end_date: 2024-11-01
location: Madrid, Spain
name: 'DISC: Symposium on Distributed Computing'
start_date: 2024-10-28
corr_author: '1'
date_created: 2024-11-17T23:01:47Z
date_published: 2024-10-24T00:00:00Z
date_updated: 2025-12-02T13:51:28Z
day: '24'
ddc:
- '000'
department:
- _id: MoHe
doi: 10.4230/LIPIcs.DISC.2024.21
ec_funded: 1
external_id:
arxiv:
- '2302.11988'
isi:
- '001542467600021'
file:
- access_level: open_access
checksum: d6c8277331cafa188c33ba1717206cf4
content_type: application/pdf
creator: dernst
date_created: 2024-11-18T08:02:45Z
date_updated: 2024-11-18T08:02:45Z
file_id: '18561'
file_name: 2024_LIPIcs_ElHayek.pdf
file_size: 809666
relation: main_file
success: 1
file_date_updated: 2024-11-18T08:02:45Z
has_accepted_license: '1'
intvolume: ' 319'
isi: 1
language:
- iso: eng
month: '10'
oa: 1
oa_version: Published Version
project:
- _id: bd9e3a2e-d553-11ed-ba76-8aa684ce17fe
grant_number: P33775
name: Fast Algorithms for a Reactive Network Layer
- _id: bd9ca328-d553-11ed-ba76-dc4f890cfe62
call_identifier: H2020
grant_number: '101019564'
name: The design and evaluation of modern fully dynamic data structures
- _id: 34def286-11ca-11ed-8bc3-da5948e1613c
grant_number: Z00422
name: Efficient algorithms
- _id: bda196b2-d553-11ed-ba76-8e8ee6c21103
grant_number: I05982
name: Static and Dynamic Hierarchical Graph Decompositions
publication: 38th International Symposium on Distributed Computing
publication_identifier:
isbn:
- '9783959773522'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
scopus_import: '1'
status: public
title: Broadcast and Consensus in stochastic dynamic networks with Byzantine nodes
and adversarial edges
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
volume: 319
year: '2024'
...