---
_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. <i>14th Innovations in Theoretical Computer Science Conference</i>. Vol
    251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2023. doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2023.47">10.4230/LIPICS.ITCS.2023.47</a>'
  apa: 'El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2023). Asymptotically tight
    bounds on the time complexity of broadcast and its variants in dynamic networks.
    In Y. Tauman Kalai (Ed.), <i>14th Innovations in Theoretical Computer Science
    Conference</i> (Vol. 251). Cambridge, Massachusetts, USA: Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik. <a href="https://doi.org/10.4230/LIPICS.ITCS.2023.47">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>'
  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 <i>14th Innovations in Theoretical Computer Science Conference</i>, edited
    by Yael Tauman Kalai, Vol. 251. Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2023. <a href="https://doi.org/10.4230/LIPICS.ITCS.2023.47">https://doi.org/10.4230/LIPICS.ITCS.2023.47</a>.
  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 <i>14th
    Innovations in Theoretical Computer Science Conference</i>, 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.” <i>14th Innovations in Theoretical
    Computer Science Conference</i>, edited by Yael Tauman Kalai, vol. 251, 47, Schloss
    Dagstuhl - Leibniz-Zentrum für Informatik, 2023, doi:<a href="https://doi.org/10.4230/LIPICS.ITCS.2023.47">10.4230/LIPICS.ITCS.2023.47</a>.
  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
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
license: https://creativecommons.org/licenses/by/4.0/
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'
...