A simple population protocol for fast robust approximate majority
A simple population protocol for fast robust approximate majority
复制标题
DOI：
10.1007/s00446-008-0059-z
复制
发表时间：
2008-07-01
影响因子：
1.3
通讯作者：
Eisenstat, David
中科院分区：
文献类型：
--
作者：
Angluin, Dana;Aspnes, James;Eisenstat, David
我们描述并分析了一个三状态单向种群协议，以计算模型中的近似多数，其中代理对是随机均匀抽取进行交互的。给定x、y和包含至少一个非空白的空白的初始配置，目标是使代理在值x或y之一上达成共识。此外，选择的值应该是多数非空初始值，只要它超过少数足够的幅度。我们证明了高概率n代理达成共识，在O（n log n）的相互作用和选择的值是大多数，其初始利润率至少是欧米茄（根n log n）。该协议具有容忍代理的o（root n）中的拜占庭行为的附加属性，使其成为第一个容忍拜占庭代理的已知人口协议。
We describe and analyze a 3-state one-way population protocol to compute approximate majority in the model in which pairs of agents are drawn uniformly at random to interact. Given an initial configuration of x's, y's and blanks that contains at least one non-blank, the goal is for the agents to reach consensus on one of the values x or y. Additionally, the value chosen should be the majority non-blank initial value, provided it exceeds the minority by a sufficient margin. We prove that with high probability n agents reach consensus in O(n log n) interactions and the value chosen is the majority provided that its initial margin is at least omega(root n log n). This protocol has the additional property of tolerating Byzantine behavior in o(root n) of the agents, making it the first known population protocol that tolerates Byzantine agents.