Lower bounds for the noisy broadcast problem

We prove the first nontrivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n + 1 processors P₀, P₁, ..., P_n. Each P_i, for i ≥ 1, initially has a private bit x_i and the goal is for P₀ to learn f (x_l, ..., x_n) for some specified function f. At each time step, a designated processor broadcasts some function of its private bit and the bits it has heard so far. Each broadcast is received by the other processors but each reception may be corrupted by noise. In this model, Gallager (1988) gave a noise-resistant protocol that allows P₀ to learn the entire input in O(n log log n) broadcasts. We prove that Gallager´s protocol is optimal up to a constant factor. Our lower bound follows from a lower bound in a new model, the generalized noisy decision tree model, which may be of independent interest.