Lower bounds for the noisy broadcast problem
Lower bounds for the noisy broadcast problem
复制标题
噪声广播问题的下界
DOI：
10.1109/sfcs.2005.48
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
Michael E. Saks
中科院分区：
文献类型：
--
作者：
Navin Goyal;Guy Kindler;Michael E. Saks
我们证明了第一个非平凡的（超线性）下界在嘈杂的广播模型的分布式计算。在该模型中，有n + 1个处理器P/sub 0/，P/sub 1/，.，P/sub n/。对于i /spl ges/ 1，每个P/sub i/最初具有私有位x/sub i/，并且对于P/sub 0/，目标是学习f（x/sub i/，.，x/sub n/），对于某个特定的函数f。在每一个时间步，一个指定的处理器广播它的私有位和它到目前为止听到的位的一些功能。每个广播由其他处理器接收，但是每个接收可能被噪声破坏。在这个模型中，Gallager（1988）给出了一个抗噪声协议，允许P/sub 0/在O（n log log n）广播中学习整个输入。我们证明了Gallager的协议是最佳的常数因子。我们的下界来自一个新的模型，广义噪声决策树模型，这可能是独立的利益的下界。
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/sub 0/, P/sub 1/, ..., P/sub n/. Each P/sub i/, for i /spl ges/ 1, initially has a private bit x/sub i/ and the goal is for P/sub 0/ to learn f (x/sub l/, ..., x/sub 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/sub 0/ 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.