Broadcasting in dynamic radio networks
Copyright policy )Broadcasting in dynamic radio networks
AbstractIt is reasonable to claim that almost all major questions related to radio broadcasting can be considered closed as far as static networks are considered: the network never changes during the entire protocol's execution. On the other hand, theoretical results on communication protocols in any scenario where the network topology may change during protocol's execution (i.e. a dynamic radio network) are very few.In this paper, we present a theoretical study of broadcasting in radio networks having dynamic unknown topology. The dynamic network is modeled by means of adversaries: we consider two of them. We first analyze an oblivious, memoryless random adversary that can be seen as the dynamic version of the average-case study presented by Elsässer and Gasieniec in JCSS, 2006. We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). This is the dynamic version of the worst-case study provided by Bar-Yehuda, Goldreich and Itai in JCSS, 1992.In both cases we provide tight bounds on the completion time of randomized broadcast protocols.
Randomized algorithm, Dynamic network, 000, Dynamic networks, Computer Networks and Communications, Applied Mathematics, Randomized algorithms, Settore MAT/06 - PROBABILITA' E STATISTICA MATEMATICA, Random graph, Settore INF/01 - INFORMATICA, Radio network, Theoretical Computer Science, Randomized algorithms; Dynamic networks; Radio networks; Random graphs, Radio networks, Computer Networks and Communication, Computational Theory and Mathematics, dynamic networks; radio networks; random graphs; randomized algorithms, Dynamic networks; Radio networks; Random graphs; Randomized algorithms; Computer Networks and Communications;, Random graphs
Randomized algorithm, Dynamic network, 000, Dynamic networks, Computer Networks and Communications, Applied Mathematics, Randomized algorithms, Settore MAT/06 - PROBABILITA' E STATISTICA MATEMATICA, Random graph, Settore INF/01 - INFORMATICA, Radio network, Theoretical Computer Science, Randomized algorithms; Dynamic networks; Radio networks; Random graphs, Radio networks, Computer Networks and Communication, Computational Theory and Mathematics, dynamic networks; radio networks; random graphs; randomized algorithms, Dynamic networks; Radio networks; Random graphs; Randomized algorithms; Computer Networks and Communications;, Random graphs
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).30 popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network.Top 10% influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically).Top 10% impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network.Top 10%
Citations provided by BIP!Popularity provided by BIP!