We consider the problems of deterministic broadcasting and gossiping in
completely unknown ad-hoc radio networks. We assume that nothing is known to
the nodes about the topology or even the size of the network, $n$, except that
$n > 1$. Protocols for vanilla model, when $n$ is known, may be run for
increasingly larger estimates $2^i$ on the size of the network, but one cannot
determine when such a protocol should terminate. Thus, to carry this design
paradigm, successful completion or in-completion of the process should be
detected, and this knowledge circulated in the network. We consider the problem
of deterministic Acknowledged Broadcasting and Gossiping when nodes can take
polynomially large labels.

For the above setting, we present the following results for strongly
connected networks: (a) A deterministic protocol for acknowledged broadcasting
which takes $NRG(n,n^c)$ rounds, where $NRG(n,n^c)$ is the round complexity of
deterministic gossiping for vanilla model. (b) A deterministic protocol for
acknowledged gossiping, which takes $O(n^2 \lg n)$ rounds when collision
detection mechanism is available. The structure of the transmissions of nodes
in the network, to enable them to infer collisions, and discover existence of
unknown in-neighborhood as a result, is abstracted as a family of integral sets
called Selecting-Colliding family. We prove the existence of
Selecting-Colliding families using the probabilistic method and employ them to
design protocol for acknowledged gossiping when no collision detection
mechanism is available.

Finally, we present a deterministic protocol for acknowledged broadcasting
for bidirectional networks, with a round complexity of $O(n \lg n)$ rounds.