---
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: <i>Proceedings of the ACM Symposium on Principles
    of Distributed Computing</i>. Association for Computing Machinery; 2022:54-56.
    doi:<a href="https://doi.org/10.1145/3519270.3538460">10.1145/3519270.3538460</a>'
  apa: 'El-Hayek, A., Henzinger, M., &#38; Schmid, S. (2022). Brief announcement:
    Broadcasting time in dynamic rooted trees is linear. In <i>Proceedings of the
    ACM Symposium on Principles of Distributed Computing</i> (pp. 54–56). Salerno,
    Italy: Association for Computing Machinery. <a href="https://doi.org/10.1145/3519270.3538460">https://doi.org/10.1145/3519270.3538460</a>'
  chicago: 'El-Hayek, Antoine, Monika Henzinger, and Stefan Schmid. “Brief Announcement:
    Broadcasting Time in Dynamic Rooted Trees Is Linear.” In <i>Proceedings of the
    ACM Symposium on Principles of Distributed Computing</i>, 54–56. Association for
    Computing Machinery, 2022. <a href="https://doi.org/10.1145/3519270.3538460">https://doi.org/10.1145/3519270.3538460</a>.'
  ieee: 'A. El-Hayek, M. Henzinger, and S. Schmid, “Brief announcement: Broadcasting
    time in dynamic rooted trees is linear,” in <i>Proceedings of the ACM Symposium
    on Principles of Distributed Computing</i>, 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.” <i>Proceedings of the ACM Symposium on Principles of
    Distributed Computing</i>, Association for Computing Machinery, 2022, pp. 54–56,
    doi:<a href="https://doi.org/10.1145/3519270.3538460">10.1145/3519270.3538460</a>.'
  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'
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'
...