Gathering Despite Mischief
Gathering Despite Mischief
复制标题
尽管恶作剧但仍聚集在一起
DOI：
--
复制
发表时间：
2012
期刊：
影响因子：
--
通讯作者：
D. Peleg
中科院分区：
文献类型：
--
作者：
Yoann Dieudonné;A. Pelc;D. Peleg
由未知数量的移动的代理组成的团队，从未知网络的不同节点开始，必须在同一节点会面。代理在同步轮中移动。每个代理都有不同的标签。多达f个代理人是拜占庭人。我们考虑两个层次的拜占庭行为。强拜占庭代理可以在移动时选择任意端口，并可以向其他代理传递任意信息，而弱拜占庭代理可以做同样的事情，除了改变其标签。什么是最小数量的好代理，保证所有的确定性收集，与终止？我们完全解决这个拜占庭收集问题在任意网络弱拜占庭代理，并给出近似的解决方案，强拜占庭代理，当网络的大小是已知的，当它是未知的。事实证明，拜占庭行为的强弱以及网络大小的知识都会显著影响结果。对于弱拜占庭代理，我们表明，任何数量的好代理允许解决问题的网络已知的大小。如果大小未知，则这个最小数是f+2。更确切地说，我们展示了一个确定性多项式算法，它可以在任意网络中收集所有好的代理，前提是至少有f+2个代理。我们还提供了一个匹配的下限：我们证明，如果好的代理的数量是最多f+1，那么他们是不能够收集确定性与终止在某些网络。对于强拜占庭代理，我们给出了一个下界的f+1，即使当图是已知的：我们表明，f好的代理不能收集确定性的f拜占庭代理的存在下，即使在一个环的已知大小。在积极的一面，我们给出了确定性的收集算法，至少2f+1个好的代理时，网络的大小是已知的，至少4f+2个好的代理时，它是未知的。
A team consisting of an unknown number of mobile agents, starting from different nodes of an unknown network, have to meet at the same node. Agents move in synchronous rounds. Each agent has a different label. Up to f of the agents are Byzantine. We consider two levels of Byzantine behavior. A strongly Byzantine agent can choose an arbitrary port when it moves and it can convey arbitrary information to other agents, while a weakly Byzantine agent can do the same, except changing its label. What is the minimum number of good agents that guarantees deterministic gathering of all of them, with termination? We solve exactly this Byzantine gathering problem in arbitrary networks for weakly Byzantine agents and give approximate solutions for strongly Byzantine agents, both when the size of the network is known and when it is unknown. It turns out that both the strength versus the weakness of Byzantine behavior and the knowledge of network size significantly impact the results. For weakly Byzantine agents, we show that any number of good agents permits solving the problem for networks of known size. If the size is unknown, then this minimum number is f+2. More precisely, we show a deterministic polynomial algorithm that gathers all good agents in an arbitrary network, provided that there are at least f+2 of them. We also provide a matching lower bound: we prove that if the number of good agents is at most f+1, then they are not able to gather deterministically with termination in some networks. For strongly Byzantine agents, we give a lower bound of f+1, even when the graph is known: we show that f good agents cannot gather deterministically in the presence of f Byzantine agents even in a ring of known size. On the positive side, we give deterministic gathering algorithms for at least 2f+1 good agents when the size of the network is known and for at least 4f+2 good agents when it is unknown.