Lower Bounds for Noisy Computations

We consider noisy distributed computation in the setting of wireless sensor networks, where processors are placed randomly on a unit square. They communicate with each other by broadcasting messages in order to compute some function whose input is distributed among them. Constraints on power usage limit the range and the number of transmissions. Furthermore, messages often get corrupted during transmission. Recently, protocols have been proposed to compute efficiently in this model. We show the first lower bounds in this model: in order to compute the PARITY or MAJORITY of N bits reliably, at least N log log N transmission are necessary. This shows that the currently known protocols for these functions are optimal. The techniques developed in this work can also be used to prove lower bounds for noisy decision trees.