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.
dynamic networks; radio networks; random graphs; randomized algorithms
01 Pubblicazione su rivista::01a Articolo in rivista
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].
File allegati a questo prodotto
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11573/229513
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 30
  • ???jsp.display-item.citation.isi??? 24
social impact