Perfect information leader election in log*n+O(1) rounds
Perfect information leader election in log*n+O(1) rounds
复制标题
log*n O(1) 轮完美信息领导者选举
DOI：
10.1109/sfcs.1998.743508
复制
发表时间：
1998
期刊：
影响因子：
--
通讯作者：
David Zuckerman
中科院分区：
文献类型：
--
作者：
A. Russell;David Zuckerman
在领袖选举问题中，n个参与者希望随机选出一个领袖。困难在于，一些参与者的联盟可能会密谋选举自己的一名成员。我们采用了完美的信息模型：所有的通信都是通过广播进行的，而坏玩家拥有无限的计算能力。在一轮比赛中，他们也可能会等着看优秀球员的表现。一个协议被称为弹性的，如果一个好的领导者被选举的概率从0开始。我们给出了一个简单的，建设性的领导者选举协议，是弹性对联盟的大小/spl beta/n，任何/spl beta/<1/2。我们的协议需要log*n+O（1）轮，每个参与者每轮最多发送log n位。对于任何常数k，我们的协议可以修改为进行k轮，并且对大小为/spl epsi/n（log/sup（k）/n）/sup 3/的联盟具有弹性，其中/spl epsi/是足够小的常数，log（k）表示对数迭代k次。这对于k/spl ges/3是有建设性的。
In the leader election problem, n players wish to elect a random leader. The difficulty is that some coalition of players may conspire to elect one of its own members. We adopt the perfect information model: all communication is by broadcast, and the bad players have unlimited computational power. Within a round, they may also wait to see the inputs of the good players. A protocol is called resilient if a good leader is elected with probability bounded away from 0. We give a simple, constructive leader election protocol that is resilient against coalitions of size /spl beta/n, for any /spl beta/<1/2. Our protocol takes log*n+O(1) rounds, each player sending at most log n bits per round. For any constant k, our protocol can be modified to take k rounds and be resilient against coalitions of size /spl epsi/n(log/sup (k)/n)/sup 3/, where /spl epsi/ is a small enough constant and log(k) denotes the logarithm iterated k times. This is constructive for k/spl ges/3.