|
Abstract : |
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 identi cation 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 2, |
