It 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 Elsasser 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. (C) 2008 Elsevier Inc. All rights reserved.
Broadcasting in dynamic radio networks / Andrea E. F., Clementi; Monti, Angelo; Francesco, Pasquale; Silvestri, Riccardo. - In: JOURNAL OF COMPUTER AND SYSTEM SCIENCES. - ISSN 0022-0000. - STAMPA. - 75:4(2009), pp. 213-230. (Intervento presentato al convegno 26th Annual ACM Symposium on Principles of Distributed Computing tenutosi a Portland, OR nel 2007) [10.1016/j.jcss.2008.10.004].
Broadcasting in dynamic radio networks
MONTI, Angelo;SILVESTRI, RICCARDO
2009
Abstract
It 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 Elsasser 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. (C) 2008 Elsevier Inc. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.