We study the completion time of distributed broadcast protocols in dynamic radio networks. The dynamic network is modelled by means of adversaries: we consider two of them that somewhat are the extremal cases. We first analyze the weakest one, i.e., an oblivious, memoryless random adversary. At each time slot t, a graph Gt is selected according to the well-known random graph model Gn,p. We derive a randomized protocol that, on input nand p, completes broadcasting in O(logn) time. Then, we prove that any randomized protocol has (logn)completion time. When p is unknown, we present an oblivious homogeneous version of the Bar Yehuda-Goldreich-Itai's randomized protocol having O(log2n) completion time and we prove a lower bound (log 2 n/loglogn) that holds for any randomized oblivious homogeneous protocol. We emphasize that the above (poly-)logarithmic upper bounds also hold when random graphs are sparse and disconnected, i.e., for p=o(lnn/n). We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). Up to now, it is not even known whether finite expected completion time is achievable against this adversary. We present a simple randomized protocol that works in O(n 2/log n) completion time. This bound is then shown to be optimal. Copyright © 2007 ACM.

Communication in dynamic radio networks / Andrea E. F., Clementi; Francesco, Pasquale; Monti, Angelo; Silvestri, Riccardo. - STAMPA. - (2007), pp. 205-214. ((Intervento presentato al convegno PODC'07: 26th Annual ACM Symposium on Principles of Distributed Computing tenutosi a Portland, OR nel 12 August 2007 through 15 August 2007 [10.1145/1281100.1281131].

Communication in dynamic radio networks

MONTI, Angelo;SILVESTRI, RICCARDO
2007

Abstract

We study the completion time of distributed broadcast protocols in dynamic radio networks. The dynamic network is modelled by means of adversaries: we consider two of them that somewhat are the extremal cases. We first analyze the weakest one, i.e., an oblivious, memoryless random adversary. At each time slot t, a graph Gt is selected according to the well-known random graph model Gn,p. We derive a randomized protocol that, on input nand p, completes broadcasting in O(logn) time. Then, we prove that any randomized protocol has (logn)completion time. When p is unknown, we present an oblivious homogeneous version of the Bar Yehuda-Goldreich-Itai's randomized protocol having O(log2n) completion time and we prove a lower bound (log 2 n/loglogn) that holds for any randomized oblivious homogeneous protocol. We emphasize that the above (poly-)logarithmic upper bounds also hold when random graphs are sparse and disconnected, i.e., for p=o(lnn/n). We then consider the deterministic worst-case adversary that, at each time slot, can make any network change (thus the strongest adversary). Up to now, it is not even known whether finite expected completion time is achievable against this adversary. We present a simple randomized protocol that works in O(n 2/log n) completion time. This bound is then shown to be optimal. Copyright © 2007 ACM.
PODC'07: 26th Annual ACM Symposium on Principles of Distributed Computing
radio networks; randomized algorithms
04 Pubblicazione in atti di convegno::04b Atto di convegno in volume
Communication in dynamic radio networks / Andrea E. F., Clementi; Francesco, Pasquale; Monti, Angelo; Silvestri, Riccardo. - STAMPA. - (2007), pp. 205-214. ((Intervento presentato al convegno PODC'07: 26th Annual ACM Symposium on Principles of Distributed Computing tenutosi a Portland, OR nel 12 August 2007 through 15 August 2007 [10.1145/1281100.1281131].
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/238213
 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??? 22
social impact