Ahmadi, MohamadMohamadAhmadiGhodselahi, AbdolhamidAbdolhamidGhodselahiKuhn, FabianFabianKuhnMolla, Anisur RahamanAnisur RahamanMolla2020-01-272020-01-272020-02-02Theoretical Computer Science (806): 363-387 (2020-02-02)http://hdl.handle.net/11420/4591We study the time complexity of single and multi token broadcast in adversarial dynamic radio networks. Initially, k tokens (which are k pieces of information) are distributed among the n nodes of a network and all the tokens need to be disseminated to all the nodes in the network. We first consider the single-token broadcast problem (i.e., the case k=1). By presenting upper and lower bounds, we show that the time complexity of single-token broadcast depends on the amount of stability and connectivity of the dynamic network topology and on the adaptiveness of the adversary providing the dynamic topology. Then, we give two generic algorithms which allow to transform generalized forms of single-token broadcast algorithms into multi-token broadcast (k-token broadcast) algorithms. Based on these generic algorithms, we obtain k-token broadcast algorithms for a number of different dynamic network settings. For one of the modeling assumptions, our algorithm is complemented by a lower bound which shows that the upper bound is close to optimal.en0304-39752020363387Dynamic networkGlobal broadcastHitting gameInformation disseminationInterval connectivityRadio networkJournal Article10.1016/j.tcs.2019.07.013Other