Time complexity of radio broadcasting: Adaptiveness vs. obliviousness and randomization vs. determinism

We consider the time of broadcasting in ad hoc radio networks modeled as undirected graphs. In such networks, every node knows only its own label and a linear bound on the number of nodes but is unaware of the topology of the network, or even of its own neighborhood. Our aim is to study to what extent the availability of two important characteristics of a broadcasting algorithm influences optimal broadcasting time. These characteristics are adaptiveness and randomization. Our contribution is establishing upper and lower bounds on optimal broadcasting time for three classes of algorithms: adaptive deterministic, oblivious randomized and oblivious deterministic. In two cases we present tight bounds, and in one case a small gap remains. We show that for deterministic adaptive algorithms time Ω(n) is required even for n-node networks of constant diameter. This lower bound is strongest possible, since linear time algorithms are known, and hence establishes optimal time Θ(n) for this class. For oblivious randomized algorithms we show an upper bound O(nmin{D,logn}) and a lower bound Ω(n) on optimal expected broadcasting time in n-node networks of diameter D. Finally, for oblivious deterministic algorithms we show matching upper and lower bounds Θ(nmin{D,n}) on optimal broadcasting time. Our results imply that enforcing obliviousness has at least as strong negative impact on broadcasting time as enforcing determinism, and that algorithms having both these features are strictly less efficient than those having only one of them.