Synchronous Consensus with Mortal Byzantines
Synchronous Consensus with Mortal Byzantines
复制标题
与凡人拜占庭人同步达成共识
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
J. Blanquart
中科院分区：
文献类型：
--
作者：
Josef Widder;G. Gridling;Bettina Weiss;J. Blanquart
我们考虑的问题，达成协议的同步系统下的故障模型，其严重程度介于拜占庭和崩溃故障。对于这些“致命的”拜占庭故障，我们假设故障进程在最终崩溃之前采取有限数量的任意步骤。在讨论了几个应用程序的例子，这个模型是合理的，我们提出并证明正确的共识算法，容忍少数错误的进程，即，与经典的拜占庭故障相比，可以容忍更多的故障。我们还表明，该算法是最佳的所需数量的进程，没有算法可以解决共识，只有大多数正确的进程在有限数量的轮下，我们的故障假设。最后，我们考虑更多的限制故障模型，允许进一步减少所需的进程数。
We consider the problem of reaching agreement in synchronous systems under a fault model whose severity lies between Byzantine and crash faults. For these "mortal" Byzantine faults, we assume that faulty processes take a finite number of arbitrary steps before they eventually crash. After discussing several application examples where this model is justified, we present and prove correct a consensus algorithm that tolerates a minority of faulty processes; i.e., more faults can be tolerated compared to classic Byzantine faults. We also show that the algorithm is optimal regarding the required number of processes and that no algorithm can solve consensus with just a majority of correct processes in a bounded number of rounds under our fault assumption. Finally, we consider more restricted fault models that allow to further reduce the required number of processes.