Oblivious gossiping in ad-hoc radio networks
Bogdan S. Chlebus, Leszek Antoni Gąsieniec, Andrzej Lingas, Aris Pagourtzis · 2001
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.