loading...
Lower Bounds for the Noisy Broadcast Problem
Pittsburgh, Pennsylvania, USA October 23-October 25
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/SFCS.2005.4846th Annual IEEE Symposium on Foundat ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Navin Goyal, Dept. of Computer Science Rutgers University
Guy Kindler, Princeton University
Michael Saks, Dept. of Mathematics Rutgers University

We prove the first non-trivial (superlinear) lower bound in the noisy broadcast model of distributed computation. In this model, there are n + 1 processors P0, P1,..., Pn. Each Pi, for i \ge 1, initially has a private bit xi and the goal is for P0 to learn f(x1, . . . , xn) 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 [16] gave a noise-resistant protocol that allows P0 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.

Citation:
Navin Goyal, Guy Kindler, Michael Saks, "Lower Bounds for the Noisy Broadcast Problem," focs, pp.40-52, 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05), 2005
Usage of this product signifies your acceptance of the Terms of Use.