---
OA_place: publisher
OA_type: gold
_id: '22327'
abstract:
- lang: eng
text: "Population protocols are a model of distributed computing where\r\n\U0001D45B
agents, each a simple finite-state machine, interact in pairs to\r\nsolve a common
task against a (adversarial) interaction scheduler.\r\nThis model was intensively
studied in recent years; in particular,\r\nthe problem of relative majority received
much attention: Each\r\nagent starts with an input opinion (or color) out of \U0001D458
possibilities,\r\nand the goal is for each agent to eventually output the color
with\r\nthe largest support in the population. Before our work, the state\r\ncomplexity
(the minimum number of states required per agent) was\r\nonly known to be between
Ω(\U0001D458\r\n2\r\n) and\U0001D442(\U0001D458\r\n7\r\n). Our main contribution\r\nis
a population protocol that solves the relative majority problem\r\nwith \U0001D458\r\n3\r\nstates.
We achieve this result with a new protocol called\r\nCircles. While prior approaches
in the literature relied on duels of\r\nagents to find the majority color — an
approach that proved effective\r\nfor the case with two colors — Circles partitions
the agents into\r\ncircular linked lists of decreasing sizes, with the property
that no\r\ntwo agents with the same initial color lie in the same circle. We\r\nshow
that Circles always correctly computes the desired structure\r\nagainst the most
adversarial of schedulers (weakly fair). We then\r\nshow that a trivial extension
of Circles solves the relative majority\r\nproblem. We extend our protocol to
handle various tie-breaking\r\nmechanisms or to support the case where the agents
do not share a\r\nprior ordering of the colors. Finally, we show that a modification
of\r\nCircles solves the ranking problem with 2 · \U0001D458^4\r\nstates, where
each\r\nagent must output the rank of its initial color in the population."
acknowledgement: "Funded by the European union. Views and opinions expressed are\r\nhowever
those of the author(s) only and do not necessarily reflect\r\nthose of the European
Union or the European Research Council\r\nExecutive Agency. Neither the European
Union nor the granting authority can be held responsible for them. This project
has received\r\nfunding from the European Research Council (ERC) under the European
Union’s Horizon 2020 research and innovation programme\r\n(MoDynStruct, No. 101019564)
and the Austrian Science\r\nFund (FWF) grant DOI 10.55776/I5982. For open access
purposes,\r\nthe author has applied a CC BY public copyright license to any\r\nauthor-accepted
manuscript version arising from this submission."
article_processing_charge: Yes
arxiv: 1
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. Ranking opinions with few states
in population protocols. In: Proceedings of the ACM Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2026:414-424.
doi:10.1145/3796701.3815913'
apa: 'Breitkopf, T.-L., Dallot, J., El-Hayek, A., & Schmid, S. (2026). Ranking
opinions with few states in population protocols. In Proceedings of the ACM
Symposium on Principles of Distributed Computing (pp. 414–424). Egham, United
Kingdom: Association for Computing Machinery. https://doi.org/10.1145/3796701.3815913'
chicago: Breitkopf, Tom-Lukas, Julien Dallot, Antoine El-Hayek, and Stefan Schmid.
“Ranking Opinions with Few States in Population Protocols.” In Proceedings
of the ACM Symposium on Principles of Distributed Computing, 414–24. Association
for Computing Machinery, 2026. https://doi.org/10.1145/3796701.3815913.
ieee: T.-L. Breitkopf, J. Dallot, A. El-Hayek, and S. Schmid, “Ranking opinions
with few states in population protocols,” in Proceedings of the ACM Symposium
on Principles of Distributed Computing, Egham, United Kingdom, 2026, pp. 414–424.
ista: 'Breitkopf T-L, Dallot J, El-Hayek A, Schmid S. 2026. Ranking opinions with
few states in population protocols. Proceedings of the ACM Symposium on Principles
of Distributed Computing. PODC: Symposium on Principles of Distributed Computing,
414–424.'
mla: Breitkopf, Tom-Lukas, et al. “Ranking Opinions with Few States in Population
Protocols.” Proceedings of the ACM Symposium on Principles of Distributed Computing,
Association for Computing Machinery, 2026, pp. 414–24, doi:10.1145/3796701.3815913.
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, 2026, pp. 414–424.
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: '0'
date_created: 2026-07-14T05:40:17Z
date_published: 2026-07-01T00:00:00Z
date_updated: 2026-07-22T07:49:22Z
day: '01'
ddc:
- '000'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1145/3796701.3815913
ec_funded: 1
external_id:
arxiv:
- '2605.18707'
file:
- access_level: open_access
checksum: e56da70c1b2e7e663d2d8106cf07a30a
content_type: application/pdf
creator: dernst
date_created: 2026-07-16T11:18:44Z
date_updated: 2026-07-16T11:18:44Z
file_id: '22353'
file_name: 2026_ACMPODC_Breitkopf.pdf
file_size: 702140
relation: main_file
success: 1
file_date_updated: 2026-07-16T11:18:44Z
fulldoi: https://doi.org/10.1145/3796701.3815913
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: 414 - 424
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 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: Ranking opinions with few 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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
OA_place: publisher
_id: '22281'
abstract:
- lang: eng
text: "In this thesis, we took a look at networks, and more specifically, at networks
that change over time, whether those are networks in the distributed algorithms
sense of the word, or the graph algorithm sense. \r\n\r\nIn distributed algorithms,
we looked at two main problems. First, the broadcast problem: given n agents,
each agent is tasked to forward a (unique) message to every other agent. Agents
collaborate and can copy and forward all messages they have received up until
that point. Broadcast is achieved when one agent has successfully broadcast its
message to everyone else. We studied the case where the communication network
is controlled by an adversary, under the condition that the graph is rooted in
every round of communication. We show that the adversary can delay broadcast for
at most l\r\n(1 + √\r\n2)n\r\nm\r\n rounds, improving on the $O(n\\log\\log n)$
previous upper bound~\\cite{fugger2020radius}, and asymptotically matching the
$\\sim 1.5n$ lower bound~\\cite{schwarz2017linear}.\r\n\r\nWe then looked at the
stochastic version of the problem: here, the adversary -- parametrized by $k$
where $k=0$ signifies that the adversary has no control, and $k=n$ that the adversary
has full control -- can choose parts of the graph, and the graph is then completed
stochastically. Here, we are able to look at a stronger version of broadcast:
instead of having $n$ messages trying to be broadcast in parallel, we can assume
that only one message needs to be broadcasted. We show the bound $\\Theta(k+\\log
n)$.\r\n\r\nThen, we looked at undecided states dynamics in population protocols:
given a population of $n$ agents, where each initially holds an opinion among
$k$ different ones. In each round, two agents are chosen uniformly at random,
and can interact. If they have different opinions, they forget their opinions
and become undecided. If one of them is undecided while the other has an opinion,
they undecided agent copies they opinion of the decided one. The question is then,
how many interactions does it take for the whole population to share the same
opinion? We show a $\\Omega(kn\\log \\frac {\\sqrt n} {k \\log n})$ lower bound
\ for any $k = o\\left(\\frac {\\sqrt n}{\\log n}\\right)$.\r\nThis is tight for
any $ k \\le n^{\\frac 1 2 - \\epsilon}$, where $\\epsilon >0$ can be any small
constant, matching the known $O(kn\\log n)$ upper bound for $k = O\\left(\\frac
{\\sqrt n} {\\log ^2 n}\\right)$~\\cite{DBLP:conf/podc/AmirABBHKL23}.\r\n\r\nFinally,
in dynamic algorithms, we study the minimum cut problem: we are given a graph,
whose vertex set we want to partition into two subsets such that the number of
edges crossing from one subset to the other is minimized. Then, the graph can
be updated via edge insertions or deletions, and we must update the solution without
recomputing everything from scratch. We present an exact fully-dynamic minimum
cut algorithm that runs in $n^{o(1)}$ deterministic update time when the minimum
cut size is at most $2^{\\Theta(\\log^{3/4-c}n)}$ for any $c>0$, improving on
the previous algorithm~\\cite{DBLP:conf/soda/JinST24} whose minimum cut size limit
is $(\\log n)^{o(1)}$. Using sparsification and randomization techniques, we are
able to extend this to all values of the minimum cut in weighted graphs, at the
cost of a $(1+o(1))$-approximation ratio."
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)\r\n\"The Design and Evaluation of Modern Fully Dynamic
Data Structures\" , from the\r\nAustrian Science Fund (FWF) grant DOI 10.55776/I5982
\"Static and Dynamic Hierarchical\r\nGraph Decompositions\", and from the Austrian
Science Fund (FWF) and netIDEE SCIENCE\r\nproject P 33775-N, \"Fast Algorithms for
a Reactive Network Layer\".\r\n"
alternative_title:
- ISTA Thesis
article_processing_charge: No
author:
- first_name: Antoine
full_name: El-Hayek, Antoine
id: 888a098e-fcac-11ee-aff7-d347be57b725
last_name: El-Hayek
orcid: 0000-0003-4268-7368
citation:
ama: 'El-Hayek A. Handling updates and failures: Dynamic graph algorithms and distributed
computing on dynamic networks. 2026. doi:10.15479/AT-ISTA-22281'
apa: 'El-Hayek, A. (2026). Handling updates and failures: Dynamic graph algorithms
and distributed computing on dynamic networks. Institute of Science and Technology
Austria. https://doi.org/10.15479/AT-ISTA-22281'
chicago: 'El-Hayek, Antoine. “Handling Updates and Failures: Dynamic Graph Algorithms
and Distributed Computing on Dynamic Networks.” Institute of Science and Technology
Austria, 2026. https://doi.org/10.15479/AT-ISTA-22281.'
ieee: 'A. El-Hayek, “Handling updates and failures: Dynamic graph algorithms and
distributed computing on dynamic networks,” Institute of Science and Technology
Austria, 2026.'
ista: 'El-Hayek A. 2026. Handling updates and failures: Dynamic graph algorithms
and distributed computing on dynamic networks. Institute of Science and Technology
Austria.'
mla: 'El-Hayek, Antoine. Handling Updates and Failures: Dynamic Graph Algorithms
and Distributed Computing on Dynamic Networks. Institute of Science and Technology
Austria, 2026, doi:10.15479/AT-ISTA-22281.'
short: 'A. El-Hayek, Handling Updates and Failures: Dynamic Graph Algorithms and
Distributed Computing on Dynamic Networks, Institute of Science and Technology
Austria, 2026.'
corr_author: '1'
date_created: 2026-07-13T09:39:59Z
date_published: 2026-07-13T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '13'
ddc:
- '000'
degree_awarded: PhD
department:
- _id: GradSch
- _id: MoHe
doi: 10.15479/AT-ISTA-22281
doi_confirm: '1'
ec_funded: 1
file:
- access_level: open_access
checksum: 923e4ca769c9ef2f6b0b005444faf462
content_type: application/pdf
creator: aelhayek
date_created: 2026-07-17T11:39:47Z
date_updated: 2026-07-17T11:39:47Z
file_id: '22356'
file_name: 2026_El-Hayek_Antoine_Thesis.pdf
file_size: 5465973
relation: main_file
success: 1
- access_level: closed
checksum: 262689f9df27dd6c2c7c7861f1de7329
content_type: application/x-zip-compressed
creator: aelhayek
date_created: 2026-07-17T11:40:34Z
date_updated: 2026-07-20T11:29:38Z
file_id: '22357'
file_name: 2026_El-Hayek_Antoine_Thesis.zip
file_size: 9116107
relation: source_file
file_date_updated: 2026-07-20T11:29:38Z
fulldoi: https://doi.org/10.15479/AT-ISTA-22281
has_accepted_license: '1'
language:
- iso: eng
month: '07'
oa: 1
oa_version: Published Version
page: '244'
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_identifier:
issn:
- 2663-337X
publication_status: published
publisher: Institute of Science and Technology Austria
publisher_comment: Sections 2.4 and 7.1 and chapter 6 are not CC-BY 4.0, they are
All Rights Reserved.
related_material:
record:
- id: '20051'
relation: part_of_dissertation
status: public
- id: '18557'
relation: part_of_dissertation
status: public
- id: '19982'
relation: part_of_dissertation
status: public
- id: '21720'
relation: part_of_dissertation
status: public
- id: '22374'
relation: part_of_dissertation
status: public
- id: '22373'
relation: part_of_dissertation
status: public
status: public
supervisor:
- first_name: Monika H
full_name: Henzinger, Monika H
id: 540c9bbd-f2de-11ec-812d-d04a5be85630
last_name: Henzinger
orcid: 0000-0002-5008-6530
title: 'Handling updates and failures: Dynamic graph algorithms and distributed computing
on dynamic networks'
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: dissertation
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2026'
...
---
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-07-24T12:48:29Z
day: '07'
department:
- _id: MoHe
- _id: GradSch
doi: 10.1137/1.9781611978971.25
ec_funded: 1
external_id:
arxiv:
- '2512.13105'
fulldoi: https://doi.org/10.1137/1.9781611978971.25
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'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
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
fulldoi: https://doi.org/10.4230/LIPIcs.SAND.2025.4
has_accepted_license: '1'
intvolume: ' 330'
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: 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: 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: '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: 2026-07-24T12:48:28Z
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
fulldoi: https://doi.org/10.1145/3732772.3733505
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'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
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: 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: 2026-07-24T12:48:28Z
day: '07'
department:
- _id: MoHe
doi: 10.1137/1.9781611978322.22
ec_funded: 1
external_id:
arxiv:
- '2412.15069'
fulldoi: https://doi.org/10.1137/1.9781611978322.22
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'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
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: 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: 2026-07-24T12:48: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
fulldoi: https://doi.org/10.4230/LIPIcs.DISC.2024.21
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'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
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'
...
---
_id: '22373'
abstract:
- lang: eng
text: "Data dissemination is a fundamental task in distributed computing. This paper
studies broadcast problems in various innovative models where the communication
network connecting n processes is dynamic (e.g., due to mobility or failures)
and controlled by an adversary. \r\nIn the first model, the processes transitively
communicate their ids in synchronous rounds along a rooted tree given in each
round by the adversary whose goal is to maximize the number of rounds until at
least one id is known by all processes. Previous research has shown a ⌈(3n-1)/2⌉-2
lower bound and an O(nlog log n) upper bound. We show the first linear upper bound
for this problem, namely ⌈(1+√2) n-1⌉ ≈ 2.4n.\r\nWe extend these results to the
setting where the adversary gives in each round k-disjoint forests and their goal
is to maximize the number of rounds until there is a set of k ids such that each
process knows of at least one of them. We give a ⌈3(n-k)/2⌉-1 lower bound and
a (π²+6)/6 n+1 ≈ 2.6n upper bound for this problem.\r\nFinally, we study the setting
where the adversary gives in each round a directed graph with k roots and their
goal is to maximize the number of rounds until there exist k ids that are known
by all processes. We give a ⌈3(n-3k)/2⌉+2 lower bound and a ⌈(1+√2)n⌉+k-1 ≈ 2.4n+k
upper bound for this problem.\r\nFor the two latter problems no upper or lower
bounds were previously known."
acknowledgement: " This project has received funding from the European Research Council
(ERC) under\r\nthe European Union’s Horizon 2020 research and innovation programme
(grant agreement No.\r\n101019564). This work was further supported by the Austrian
Science Fund (FWF) and netIDEE\r\nSCIENCE project P 33775-N, as well as the FWF
project I 4800-N (ADVISE)"
alternative_title:
- LIPIcs
article_number: '47'
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: Stefan
full_name: Schmid, Stefan
last_name: Schmid
orcid: 0000-0002-7798-1711
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Asymptotically tight bounds on the time
complexity of broadcast and its variants in dynamic networks. In: Tauman Kalai
Y, ed. 14th Innovations in Theoretical Computer Science Conference. Vol
251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:10.4230/LIPICS.ITCS.2023.47'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2023). Asymptotically tight
bounds on the time complexity of broadcast and its variants in dynamic networks.
In Y. Tauman Kalai (Ed.), 14th Innovations in Theoretical Computer Science
Conference (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum
für Informatik. https://doi.org/10.4230/LIPICS.ITCS.2023.47'
chicago: El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Asymptotically
Tight Bounds on the Time Complexity of Broadcast and Its Variants in Dynamic Networks.”
In 14th Innovations in Theoretical Computer Science Conference, edited
by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
2023. https://doi.org/10.4230/LIPICS.ITCS.2023.47.
ieee: A. El-Hayek, M. Henzinger, and S. Schmid, “Asymptotically tight bounds on
the time complexity of broadcast and its variants in dynamic networks,” in 14th
Innovations in Theoretical Computer Science Conference, Cambridge, Massachusetts,
USA, 2023, vol. 251.
ista: 'El-Hayek A, Henzinger M, Schmid S. 2023. Asymptotically tight bounds on the
time complexity of broadcast and its variants in dynamic networks. 14th Innovations
in Theoretical Computer Science Conference. ITCS: Innovations in Theoretical Computer
Science, LIPIcs, vol. 251, 47.'
mla: El-Hayek, Antoine, et al. “Asymptotically Tight Bounds on the Time Complexity
of Broadcast and Its Variants in Dynamic Networks.” 14th Innovations in Theoretical
Computer Science Conference, edited by Yael Tauman Kalai, vol. 251, 47, Schloss
Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:10.4230/LIPICS.ITCS.2023.47.
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, Y. Tauman Kalai (Ed.), 14th Innovations
in Theoretical Computer Science Conference, Schloss Dagstuhl - Leibniz-Zentrum
für Informatik, 2023.
conference:
end_date: 2023-01-13
location: Cambridge, Massachusetts, USA
name: 'ITCS: Innovations in Theoretical Computer Science'
start_date: 2023-01-10
date_created: 2026-07-20T11:45:04Z
date_published: 2023-02-01T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '01'
ddc:
- '000'
doi: 10.4230/LIPICS.ITCS.2023.47
editor:
- first_name: Yael
full_name: Tauman Kalai, Yael
last_name: Tauman Kalai
extern: '1'
external_id:
arxiv:
- '2211.10151'
file:
- access_level: open_access
checksum: d7f45fdcbc5fccd61db69f56d775c636
content_type: application/pdf
creator: cchlebak
date_created: 2026-07-22T08:04:03Z
date_updated: 2026-07-22T08:04:03Z
file_id: '22383'
file_name: 2023_LIPIcs_El-Hayek.pdf
file_size: 1077427
relation: main_file
success: 1
file_date_updated: 2026-07-22T08:04:03Z
fulldoi: https://doi.org/10.4230/LIPICS.ITCS.2023.47
has_accepted_license: '1'
intvolume: ' 251'
keyword:
- broadcast
- cover
- k-broadcast
- dynamic radius
- dynamic graphs
- oblivious message adversary
- time complexity
- Theory of computation → Distributed algorithms
- Networks → Network algorithms
language:
- iso: eng
month: '02'
oa: 1
oa_version: Published Version
publication: 14th Innovations in Theoretical Computer Science Conference
publication_identifier:
isbn:
- '9783959772631'
issn:
- 1868-8969
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: Asymptotically tight bounds on the time complexity of broadcast and its variants
in dynamic networks
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: 8b945eb4-e2f2-11eb-945a-df72226e66a9
volume: 251
year: '2023'
...
---
OA_place: publisher
OA_type: green
_id: '22374'
abstract:
- lang: eng
text: We study the broadcast problem on dynamic networks with n processes. The processes
communicate in synchronous rounds along an arbitrary rooted tree. The sequence
of trees is given by an adversary whose goal is to maximize the number of rounds
until at least one process reaches all other processes. Previous research has
shown a ⌈(3n-1)/(2)⌉-2 lower bound and an O(n log log n) upper bound. We show
the first linear upper bound for this problem, namely ⌈(1 + √2) n-1⌉ ~2.4n. Our
result follows from a detailed analysis of the evolution of the adjacency matrix
of the network over time.
acknowledgement: "This project has received funding from the European Research\r\nCouncil
(ERC) under the European Union’s Horizon 2020 research\r\nand innovation programme
(grant agreement No. 101019564). This\r\nwork was further supported by the Austrian
Science Fund (FWF)\r\nand netIDEE SCIENCE project P 33775-N, and by the Federal
Ministry of Education and Research (BMBF, Germany), 6G-RIC under\r\nGrant 16KISK020K.
We would like to thank Kyrill Winkler for his\r\ninputs and feedback on this paper.\r\n"
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: Stefan
full_name: Schmid, Stefan
last_name: Schmid
citation:
ama: 'El-Hayek A, Henzinger M, Schmid S. Brief announcement: Broadcasting time in
dynamic rooted trees is linear. In: Proceedings of the ACM Symposium on Principles
of Distributed Computing. Association for Computing Machinery; 2022:54-56.
doi:10.1145/3519270.3538460'
apa: 'El-Hayek, A., Henzinger, M., & Schmid, S. (2022). Brief announcement:
Broadcasting time in dynamic rooted trees is linear. In Proceedings of the
ACM Symposium on Principles of Distributed Computing (pp. 54–56). Salerno,
Italy: Association for Computing Machinery. https://doi.org/10.1145/3519270.3538460'
chicago: 'El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Brief Announcement:
Broadcasting Time in Dynamic Rooted Trees Is Linear.” In Proceedings of the
ACM Symposium on Principles of Distributed Computing, 54–56. Association for
Computing Machinery, 2022. https://doi.org/10.1145/3519270.3538460.'
ieee: 'A. El-Hayek, M. Henzinger, and S. Schmid, “Brief announcement: Broadcasting
time in dynamic rooted trees is linear,” in Proceedings of the ACM Symposium
on Principles of Distributed Computing, Salerno, Italy, 2022, pp. 54–56.'
ista: 'El-Hayek A, Henzinger M, Schmid S. 2022. Brief announcement: Broadcasting
time in dynamic rooted trees is linear. Proceedings of the ACM Symposium on Principles
of Distributed Computing. PODC: Symposium on Principles of Distrubuted Computing,
54–56.'
mla: 'El-Hayek, Antoine, et al. “Brief Announcement: Broadcasting Time in Dynamic
Rooted Trees Is Linear.” Proceedings of the ACM Symposium on Principles of
Distributed Computing, Association for Computing Machinery, 2022, pp. 54–56,
doi:10.1145/3519270.3538460.'
short: A. El-Hayek, M. Henzinger, S. Schmid, in:, Proceedings of the ACM Symposium
on Principles of Distributed Computing, Association for Computing Machinery, 2022,
pp. 54–56.
conference:
end_date: 2022-07-29
location: Salerno, Italy
name: 'PODC: Symposium on Principles of Distrubuted Computing'
start_date: 2022-07-25
date_created: 2026-07-20T11:46:26Z
date_published: 2022-07-21T00:00:00Z
date_updated: 2026-07-24T12:48:29Z
day: '21'
doi: 10.1145/3519270.3538460
extern: '1'
external_id:
arxiv:
- '2211.11352'
fulldoi: https://doi.org/10.1145/3519270.3538460
language:
- iso: eng
main_file_link:
- open_access: '1'
url: https://doi.org/10.1145/3519270.3538460
month: '07'
oa: 1
oa_version: Published Version
page: 54-56
publication: Proceedings of the ACM Symposium on Principles of Distributed Computing
publication_identifier:
isbn:
- '9781450392624'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
related_material:
record:
- id: '22281'
relation: dissertation_contains
status: public
scopus_import: '1'
status: public
title: 'Brief announcement: Broadcasting time in dynamic rooted trees is linear'
type: conference
user_id: 8b945eb4-e2f2-11eb-945a-df72226e66a9
year: '2022'
...