Lower bounds for leader election and collective coin-flipping in the perfect information model
Lower bounds for leader election and collective coin-flipping in the perfect information model
复制标题
完美信息模型中领导者选举和集体抛硬币的下界
DOI：
10.1145/301250.301337
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
A. Russell;M. Saks;David Zuckerman
集体抛硬币是在具有对抗性故障的分布式计算环境中产生公共随机比特的问题。我们考虑完美的信息模型：所有的通信是通过广播和腐败的球员是计算无界。该模型中的协议可能涉及许多异步回合。我们假设诚实的参与者只传递均匀随机的比特。我们证明了任何对线性规模的腐败联盟具有弹性的n人硬币翻转协议必须在第k轮中使用至少[1/2 - o（1）]log* n个通信轮或至少[log（2k-1）n]1-o（1）个通信位，其中log（j）表示迭代j次的对数。特别地，每轮使用一位的协议需要[1/2 - o（1）]log* n轮。这些界限也适用于领袖选举问题。这个结果的主要组成部分是随机变量集对布尔函数的影响的一个新的界限。最后，在一轮的情况下，使用其他方法，我们证明了一个新的约束的影响的变量集的大小为$\beta n$为$\beta > 1/3$。
Collective coin-flipping is the problem of producing common random bits in a distributed computing environment with adversarial faults. We consider the perfect information model: all communication is by broadcast and corrupt players are computationally unbounded. Protocols in this model may involve many asynchronous rounds. We assume that honest players communicate only uniformly random bits. We demonstrate that any n-player coin-flipping protocol that is resilient against corrupt coalitions of linear size must use either at least [1/2 - o(1)]log* n communication rounds or at least [log(2k-1) n]1-o(1) communication bits in the kth round, where log(j) denotes the logarithm iterated j times. In particular, protocols using one bit per round require [1/2 - o(1)]log* n rounds. These bounds also apply to the leader election problem. The primary component of this result is a new bound on the influence of random sets of variables on Boolean functions. Finally, in the one-round case, using other methods we prove a new bound on the influence of sets of variables of size $\beta n$ for $\beta > 1/3$.