Deterministic gossiping in directed ad-hoc radio networks

Tomasz Radzik

King's College London


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.

[Tomasz Radzik]
[King's College London]