Tight bound on mobile Byzantine Agreement-猫眼课题宝

DOI：

10.1016/j.tcs.2015.10.019

发表时间：

2014-10

期刊：

影响因子：

通讯作者：

中科院分区：

其他

文献类型：

作者：

François Bonnet;X. Défago;Thanh Dang Nguyen;M. Potop-Butucaru

本文研究了同步系统中的拜占庭协议问题，在同步系统中，恶意代理可以从一个进程移动到另一个进程，破坏它们的主机。早期关于该问题的工作是基于有偏模型的，正如我们在论文中所讨论的那样，这些模型给正确的进程或控制恶意代理的对手提供了不公平的优势。事实上，早期对该问题的研究假设，在恶意代理离开一个进程后，该进程(据说是被治愈的)能够立即准确地检测到它在前几轮中被破坏的事实，从而可以采取本地操作来恢复有效状态(Garay的模型)。我们找不到任何理由支持这种假设，因为它显然有利于正确的过程。在该模型下，n&gt；4t是已知的算法，其中n是进程的数量，t是恶意代理的最大数量。然而，界限的紧密性是未知的。相比之下，最近关于该问题的工作取消了检测时的假设，转而假设恶意代理可能在已修复进程的发送队列中留下了已损坏的消息，此外还处于已损坏的状态。因此，控制恶意代理的敌手除了破坏新破坏的进程发送的消息外，还可以破坏治愈的进程发送的消息，从而使有效故障的数量翻了一番。在有利于恶意代理的模型下，当且仅当n&>6 t时问题才能得到解决。本文对后一种模型进行了改进，以避免上述偏差。虽然治愈的进程可能会发送消息(基于被恶意代理破坏的状态)，但它将以正确的方式发送这些消息：即，根据算法发送消息。令人惊讶的是，在这个模型中，我们可以得到拜占庭协议的一个新的非平凡紧界。我们证明了至少需要5个t+1个处理器才能容忍t个移动的拜占庭代理，并提供了一个符合这个下界的时间最优算法，同时给出了问题的形式化描述。

This paper investigates the problem of Byzantine Agreement in a synchronous system where malicious agents can move from process to process, corrupting their host. Earlier works on the problem are based on biased models which, as we argue in the paper, give an unfair advantage either to the correct processes or to the adversary controlling the malicious agents. Indeed, earlier studies of the problem assume that, after a malicious agent has left a process, that process, said to be cured, is able to instantly and accurately detect the fact that it was corrupted in earlier rounds, and thus can take local actions to recover a valid state (Garay's model). We found no justification for that assumption which clearly favors correct processes. Under that model, an algorithm is known for n> 4 t, where n is the number of processes and t the maximum number of malicious agents. The tightness of the bound is however unknown. In contrast, more recent works on the problem remove the assumption on detection and assume instead that a malicious agent may have left corrupted messages in the send queue of a cured process in addition to a corrupted state. As a result, the adversary controlling the malicious agents can corrupt the messages sent by cured processes, in addition to those sent by the newly corrupted ones, thus doubling the number of effective faults. Under that model, which favors the malicious agents, the problem can be solved if and only if n> 6 t. In this paper, we refine the latter model to avoid the above biases. While a cured process may send messages (based on a state corrupted by the malicious agent), it will behave correctly in the way it sends those messages: ie, send messages according to the algorithm. Surprisingly, in this model we could derive a new non-trivial tight bound for Byzantine Agreement. We prove that at least 5 t+ 1 processors are needed in order to tolerate t mobile Byzantine agents and provide a time optimal algorithm that matches this lower bound, altogether with a formal specification of the problem.

Tight bound on mobile Byzantine Agreement

文献摘要

相似文献