Broadcasts in anonymous, dynamic networks: a new algorithm and impossibility results
Citation Link: https://doi.org/10.15480/882.17566
Publikationstyp
Conference Paper
Date Issued
2026-06
Sprache
English
Author(s)
TORE-DOI
First published in
Number in series
373
Article Number
6
Citation
5th Symposium on Algorithmic Foundations of Dynamic Networks, SAND 2026
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, Dagstuhl Publishing
ISBN of container
978-3-9597-7427-7
The broadcast problem is the task of disseminating a message from a single source node to all other nodes in a distributed system, ensuring that every node eventually receives the message despite possible network constraints such as delays, failures, or limited topology knowledge. In this work, we consider the broadcast problem in anonymous, synchronous, dynamic networks. A dynamic network is a network, whose topology changes over time, meaning that communication links can unpredictably appear and disappear. We present a randomized algorithm requiring O(log log n) bits of storage per node and terminating in O(m log n) rounds with high probability. It solves broadcast with stabilizing termination for anonymous, synchronous, 1-interval-connected networks using messages of size O(1). The algorithm is a non-idle-start algorithm. The best known idle-start algorithm for this problem requires O(log n) space, also a lower memory bound of ω(1) space is known. Our contribution affirmatively answers a question of Parzych and Daymude (DISC 2024). We also extend this result to dynamic networks with bounded connectivity time. Furthermore, we prove that for two variants of the broadcast problem in this setting no randomized algorithms exist.
Subjects
Distributed algorithms
dynamic networks
impossibility results
randomized algorithms
DDC Class
005: Computer Programming, Programs, Data and Security
519: Applied Mathematics, Probabilities
Publication version
publishedVersion