Deterministic Radio Broadcasting
Bogdan S. Chlebus, Leszek Gasieniec, Anna Ístlin,
and John Michael Robson
In Proc. 27th International Colloquium on Automata, Languages,
and Programming, volume 1853 of Lecture Notes in Computer Science,
pages 717-728. Springer Verlag, Berlin, 2000.
We consider broadcasting in radio networks: one node of the network knows a
message that needs to be learned by all the remaining nodes.
We seek distributed deterministic algorithms to perform this task.
Radio networks are modeled as directed graphs.
They are unknown, in the sense that nodes are not assumed
to know their neighbors, nor the size of the network,
they are aware only of their individual identifying numbers.
If more than one message is delivered to a node in a step then the node
cannot hear any of them.
Nodes cannot distinguish between such collisions and the case when no messages
have been delivered in a step.
The fastest previously known deterministic algorithm for deterministic
distributed broadcasting in unknown radio networks was presented
in [CGGPR], it worked in time O(n^(11/6)).
We develop three new deterministic distributed algorithms.
Algorithm A develops further the ideas of [CGGPR] and
operates in time O(n^1.77291)=O(n^(9/5)), for general
networks, and in time O(n^(1+a+H(a)+o(1))) for sparse networks with
in-degrees O(n^a) for a<1/2; here H is the entropy function.
Algorithm B uses a new approach and works in time
O(n^(3/2)log^(1/2) n) for general networks or O(n^(1+a+o(1))) for
Algorithm C further improves the performance for
general networks running in time O(n^(3/2)).