A Tight Lower Bound for Parity in Noisy Communication Networks

We show a tight lower bound of Ω(N log log N) on the number of transmission required to compute the parity of N bits (with constant error) in a network of N randomly placed sensors, communicating using local transmissions, and operating with power near the connectivity threshold. This result settles a question left open by Ying, Srikant and Dullerud (WiOpt 06), who showed how the sum of all N bits can be computed using O(N log log N) transmissions.

Earlier works on lower bounds for communication networks worked with the full broadcast model without using the fact that the communication in real networks is local, determined by the power of the transmitters. In fact, in full broadcast networks parity can be computed using O(N) transmissions. To obtain our lower bound we employ techniques developed by Goyal, Kindler and Saks (FOCS 05), who showed lower bounds in the full broadcast model by reducing the problem to a model of noisy decision trees. However, in order to capture the limited range of transmissions in real sensor networks, we define and work with a localized version of noisy decision trees. Our lower bound is obtained by exploiting special properties of parity computations in such decision trees.