Seminario Interdipartimentale di Algoritmica
 

Monday, December 18, 2006, 12:00 noon
Communication in Dynamic Radio Networks
Andrea Clementi
Università di Roma "Tor Vergata"

DI - Department of Computer Science
Seminar Room, third floor

Abstract:

We study the completion time of distributed broadcast protocols in \emph{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 $G_t$ is selected according to the well-known random graph model $G_{n,p}$. We derive a randomized protocol that has $O(\log n)$ completion time. Then, we prove that any randomized protocol has $\Omega(\log n)$ completion time. This tight bound holds when the protocol knows $p$. When $p$ is unknown, we present an oblivious homogeneous version of the Bar Yehuda-Goldreich-Itai's randomized protocol having $O(\log2 n)$ completion time and we prove a lower bound $\Omega(\log2 n/\log\log n)$ that holds for any randomized oblivious homogeneous protocol. We emphasize that the above (poly-)logarithmic upper bounds also hold when random graphs are, with high probability, sparse and disconnected, i.e., for $p = o( \ln n/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 \emph{finite} expected completion time is achievable against this adversary. We present a simple randomized protocol that works in $O(n2/\log n)$ completion time. This bound is then shown to be optimal. Our contribution provides the first strong analytical results on the broadcasting problem in fairly general models of dynamic radio networks. In particular, we note that the sub-quadratic upper bound against this most powerful, adaptive adversary implies that no meaningful (realistic or not) dynamic adversary strategy exists yielding exponential completion time.

Joint work with: Angelo Monti, Francesco Pasquale, and Riccardo Silvestri.