Oblivious gossiping in ad-hoc radio networks

We study oblivious deterministic and randomized algorithms for gossiping in unknown radio networks. In oblivious algorithms the fact (or probability in case of randomized algorithm) that a processor transmits or not at a given time-step depends solely on its identification number, the total number of processors and the number of the time-step. We distinguish oblivious deterministic algorithms which allow only one processor to transmit in each time-step and term them singleton algorithms. We also distinguish oblivious randomized algorithms where in each time-step all processors have equal probability of transmission, and call them uniform. The merit of oblivious algorithms, especially the singleton and uniform ones, is that they are simple and easy to implement. We observe that gossiping in unknown radio networks on n nodes can be completed in time (n - 1)(n - 2) + 4 by a singleton algorithm. On the other hand, we show that any singleton algorithm takes at least n² - O(n^7/4+ε) steps, for any ε > 0, whereas any deterministic oblivious algorithm requires at least n²/2 - O(n) steps to complete the gossiping. We prove also that there is an oblivious deterministic algorithm for gossiping working in time n² - ω(n). Next we show that a uniform oblivious randomized algorithm completes gossiping with high probability in time O(min{m, Dd} log² n), where m denotes the number of edges, D is the eccentricity and d the maximum in-degree in the network. Note that this upper bound is poly-logarithmic in n if D, d = O(poly log n). The best related deterministic gossiping algorithm, in terms of performance expressed with respect to n, D, d, has been previously given by Clementi et al. [13], it works in time O(Dd² log³ n). We prove also that the upper bound attained by our uniform oblivious randomized algorithm is asymptotically optimal (up to a log-square factor) for a wide range of parameters m, D and d in the class of uniform oblivious randomized algorithms. Finally we observe that in case of symmetric networks the aforementioned oblivious randomized algorithm completes gossiping with high probability in time O(n log² n) and that a known deterministic constructive broadcasting algorithm can be adopted to perform oblivious gossiping in time O(n^3/2).