---
res:
  bibo_abstract:
  - "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.@eng"
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Antoine
      foaf_name: El-Hayek, Antoine
      foaf_surname: El-Hayek
      foaf_workInfoHomepage: http://www.librecat.org/personId=888a098e-fcac-11ee-aff7-d347be57b725
    orcid: 0000-0003-4268-7368
  - foaf_Person:
      foaf_givenName: Monika H
      foaf_name: Henzinger, Monika H
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=540c9bbd-f2de-11ec-812d-d04a5be85630
    orcid: 0000-0002-5008-6530
  - foaf_Person:
      foaf_givenName: Stefan
      foaf_name: Schmid, Stefan
      foaf_surname: Schmid
    orcid: 0000-0002-7798-1711
  bibo_doi: 10.4230/LIPICS.ITCS.2023.47
  bibo_volume: 251
  dct_date: 2023^xs_gYear
  dct_isPartOf:
  - http://id.crossref.org/issn/1868-8969
  - http://id.crossref.org/issn/9783959772631
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_subject:
  - broadcast
  - cover
  - k-broadcast
  - dynamic radius
  - dynamic graphs
  - oblivious message adversary
  - time complexity
  - Theory of computation → Distributed algorithms
  - Networks → Network algorithms
  dct_title: Asymptotically tight bounds on the time complexity of broadcast and its
    variants in dynamic networks@
...