Lower bounds on leader election and gossiping in radio networks

We present a number of lower bounds on distributed gossiping and leader election problem in synchronous ad-hoc radio networks.

The lower bounds are considered for two classes of protocols: oblivious and adaptive. The best previously known lower bounds on these problems were linear due to an $n$-node star.

In the model of large labels we show a lower bound of $\Omega(n \log n)$ on leader election protocol and adaptive deterministic gossiping. In case of leader election problems our lower bound almost matches the best known upper bound $\cO(n \log^3 n)$.

In case of adaptive deterministic gossiping in the model of large labels the best known upper bound for symmetric networks is $\cO(n \log^3 n)$ and for directed networks is $\cO(n^{4/3} \log^4 n)$.

We also show a lower bound of $\Omega(n^2)$ on randomized oblivious gossiping.

This result holds for both Las Vegas and Monte Carlo protocols. Our lower bound is tight due to the "Round-Robin" protocol, whose complexity is $\cO(n^2)$ and is a special case of randomized oblivious gossiping.

Our last result is a lower bound of $\Omega(n^2)$ on deterministic oblivious gossiping for symmetric networks in the model of separate messages.

This matches the best known upper bound $\cO (n^2)$.