--- 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 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' ...