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 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.

Clementi, A., Monti, A., Silvestri, R. (2009). Broadcasting in Dynamic Radio Networks. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 75(4), 213-230 [10.1016/j.jcss.2008.10.004].

Broadcasting in Dynamic Radio Networks

CLEMENTI, ANDREA;
2009-06-01

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 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.
1-giu-2009
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore INF/01 - INFORMATICA
Settore MAT/06 - PROBABILITA' E STATISTICA MATEMATICA
English
Randomized algorithms; Dynamic networks; Radio networks; Random graphs
Extended Abstract appeared in Proceedings of the 26th Annual ACM Symposium on Principles of Distributed Computing, PODC 2007. N. of Citations (Google Scholar)= 19 (Conf. Version), 13 (Jou Version). Cited by: * F. Kuhn, N. Lynch, and R. Oshman 2010. In Proceedings of the 42nd ACM symposium on Theory of computing (STOC '10). ACM, 513-522. * F. Kuhn and R. Oshman 2011. SIGACT News 42, 1 (March 2011), 82-96. * M. Vojnovic and A. Proutiere 2011, in Proc. of IEEE INFOCOM'11, IEEE.
Clementi, A., Monti, A., Silvestri, R. (2009). Broadcasting in Dynamic Radio Networks. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 75(4), 213-230 [10.1016/j.jcss.2008.10.004].
Clementi, A; Monti, A; Silvestri, R
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
JCSSCMPS09.pdf

accesso aperto

Descrizione: preprint
Dimensione 267.77 kB
Formato Adobe PDF
267.77 kB Adobe PDF Visualizza/Apri

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/2108/18909
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 32
  • ???jsp.display-item.citation.isi??? 25
social impact