We study the "gossiping problem" in directed ad-hoc radio networks:
each node has initially one message and all these messages have to be
distributed to all nodes in the network. Our main result is a
deterministic algorithm that solves this problem in an $n$-node
network in time $O(n^{4/3}\log^4 n)$. The algorithm allows the labels
(identifiers) of the nodes to be polynomially large in $n$, and is
based on a novel way of using "selective families". The previous best
general, that is, dependent only on $n$, deterministic upper bounds
were $O(n^{5/3}\log^3 n)$ for networks with polynomially large node
labels~\cite{GPP-ESA-2002}, and $O(n^{3/2}\log^2 n)$ for networks with
linearly large node labels.
This is joint work with Leszek Gasieniec and Qin Xin.