  Broadcast is one of the fundamental network communication primitives. One
node of a network, called the $\mathit{source}$, has a message that has to be
learned by all other nodes. We consider the feasibility of deterministic
broadcast in radio networks. If nodes of the network do not have any labels,
deterministic broadcast is impossible even in the four-cycle. On the other
hand, if all nodes have distinct labels, then broadcast can be carried out,
e.g., in a round-robin fashion, and hence $O(\log n)$-bit labels are sufficient
for this task in $n$-node networks. In fact, $O(\log \Delta)$-bit labels, where
$\Delta$ is the maximum degree, are enough to broadcast successfully. Hence, it
is natural to ask if very short labels are sufficient for broadcast. Our main
result is a positive answer to this question. We show that every radio network
can be labeled using 2 bits in such a way that broadcast can be accomplished by
some universal deterministic algorithm that does not know the network topology
nor any bound on its size. Moreover, at the expense of an extra bit in the
labels, we get the additional strong property that there exists a common round
in which all nodes know that broadcast has been completed. Finally, we show
that 3-bit labels are also sufficient to solve both versions of broadcast in
the case where the labeling scheme does not know which node is the source.

Distributed, Parallel, and Cluster Computing