Gossiping with Unit Messages in Known Radio Networks
Leszek Antoni Gąsieniec, Igor Potapov · 2002
A gossiping is a communication primitive in which each node of the network possesses a unique message that is to be communicated to all other nodes in the network. We study the gossiping problem in known ad hoc radio networks, where during each transmission only unit messages originated at any node of the network can be transmitted successfully. We survey a number of radio network topologies. Assuming that the size (a number of nodes) of the network is n we show that the exact complexity of radio gossiping in stars is 2n–1, in rings is 2n±O(1), and on a line of processors is 3n ± O(1). We later prove that radio gossiping in free trees is harder and it requires at least 31/6n – 16 time steps to be completed. For free trees we also show a gossiping algorithm with time complexity 5n + 8. In conclusion we prove that in general graphs radio gossiping requires Ω(n log n) time, and we propose radio gossiping algorithm that works in time O(n log2 n).