Faster Communication in Ad-hoc Radio Networks

-By Qin Xin

University of Liverpool

Joint work with Leszek Gasieniec, University of Liverpool,

and Tomasz Radzik, King's College London

Time: 2:30PM May.26

Place: FIT 1-222

Abstract:

Communication in the radio networks has become popular due to the recent advent of new technologies. It is present not only in the ubiquitous cordless and cellular phones, but also in personal communication services, mobile data networks, and local area wireless networks. The radio networks, as well as other wireless communication systems, necessitate efficient implementation of communication primitives to carry out more complex communication tasks. This in return propels new algorithmic challenges in the theory of distributed computing and communication.

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 in this talk is a deterministic algorithm that solves this problem in an $n$-node network in time $O(n^{4/3}\log^{10/3} 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~\cite{CGR-FOCS-2000}.