### Abstract

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 P _{0}, P _{1}, . . . , P _{n}. Each P _{i}, for i ≥ 1, initially has a private bit x _{i} and the goal is for P _{0} to learn f(x _{1}, . . . , 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 [16] gave a noise-resistant protocol that allows P _{0} to learn the entire input in O(n log log n) broadcasts. We prove that Gallager's protocol is optimal up to a constantfactor. Our lower bound follows from a lower bound in a new model, the generalized noisy decision tree model, which may be of independent interest.

Original language | English (US) |
---|---|

Title of host publication | Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 |

Pages | 40-49 |

Number of pages | 10 |

DOIs | |

State | Published - Dec 1 2005 |

Event | 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States Duration: Oct 23 2005 → Oct 25 2005 |

### Publication series

Name | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
---|---|

Volume | 2005 |

ISSN (Print) | 0272-5428 |

### Other

Other | 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 |
---|---|

Country | United States |

City | Pittsburgh, PA |

Period | 10/23/05 → 10/25/05 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Engineering(all)

### Cite this

*Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005*(pp. 40-49). [1530700] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005). https://doi.org/10.1109/SFCS.2005.48