Lower bounds for the noisy broadcast problem

Navin Goyal, Guy Kindlert, Michael Saks

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Citations (Scopus)

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 languageEnglish (US)
Title of host publicationProceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
Pages40-49
Number of pages10
DOIs
StatePublished - Dec 1 2005
Event46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005 - Pittsburgh, PA, United States
Duration: Oct 23 2005Oct 25 2005

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2005
ISSN (Print)0272-5428

Other

Other46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005
CountryUnited States
CityPittsburgh, PA
Period10/23/0510/25/05

Fingerprint

Decision trees

All Science Journal Classification (ASJC) codes

  • Engineering(all)

Cite this

Goyal, N., Kindlert, G., & Saks, M. (2005). Lower bounds for the noisy broadcast problem. In 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
Goyal, Navin ; Kindlert, Guy ; Saks, Michael. / Lower bounds for the noisy broadcast problem. Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. 2005. pp. 40-49 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
@inproceedings{3995d4e274e14a429215a7c87437509a,
title = "Lower bounds for the noisy broadcast problem",
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.",
author = "Navin Goyal and Guy Kindlert and Michael Saks",
year = "2005",
month = "12",
day = "1",
doi = "10.1109/SFCS.2005.48",
language = "English (US)",
isbn = "0769524680",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
pages = "40--49",
booktitle = "Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005",

}

Goyal, N, Kindlert, G & Saks, M 2005, Lower bounds for the noisy broadcast problem. in Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005., 1530700, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, vol. 2005, pp. 40-49, 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005, Pittsburgh, PA, United States, 10/23/05. https://doi.org/10.1109/SFCS.2005.48

Lower bounds for the noisy broadcast problem. / Goyal, Navin; Kindlert, Guy; Saks, Michael.

Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. 2005. p. 40-49 1530700 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2005).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

TY - GEN

T1 - Lower bounds for the noisy broadcast problem

AU - Goyal, Navin

AU - Kindlert, Guy

AU - Saks, Michael

PY - 2005/12/1

Y1 - 2005/12/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=33748629917&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=33748629917&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2005.48

DO - 10.1109/SFCS.2005.48

M3 - Conference contribution

AN - SCOPUS:33748629917

SN - 0769524680

SN - 9780769524689

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

SP - 40

EP - 49

BT - Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005

ER -

Goyal N, Kindlert G, Saks M. Lower bounds for the noisy broadcast problem. In Proceedings - 46th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2005. 2005. p. 40-49. 1530700. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). https://doi.org/10.1109/SFCS.2005.48