论文标题
不完整网络中的异步拜占庭协议[技术报告]
Asynchronous Byzantine Agreement in Incomplete Networks [Technical Report]
论文作者
论文摘要
拜占庭协议问题被认为是分布式系统中的核心问题。例如，需要拜占庭协议来构建一个区块链，这是一个完全有序的记录日志。区块链是异步分布式系统，对拜占庭节点的耐断层。 在文献中，在完全连接的网络模型中研究了异步拜占庭协议问题，每个节点都可以将消息直接发送给其他每个节点。在许多实际环境中，此假设值得怀疑。实际上，节点可能需要通过不完整的网络进行通信，而拜占庭节点可能无法转发消息。此外，拜占庭节点可能无法正确行事，例如损坏的消息。因此，为了真正理解拜占庭协议，我们都需要成分：异步和不完整的通信网络。 在本文中，我们研究了不完整网络中的异步拜占庭协议问题。丹尼·多尔夫（Danny Dolev）的经典结果证明，在存在F拜占庭节点的分布式系统中，系统通信图的顶点连接至少应为（2F+1）。虽然Dolev的结果是用于同步确定性系统的结果，但我们证明了同步随机系统也相同的结合。我们通过呈现随机算法和匹配的下限来表明界限很紧。
The Byzantine agreement problem is considered to be a core problem in distributed systems. For example, Byzantine agreement is needed to build a blockchain, a totally ordered log of records. Blockchains are asynchronous distributed systems, fault-tolerant against Byzantine nodes. In the literature, the asynchronous byzantine agreement problem is studied in a fully connected network model where every node can directly send messages to every other node. This assumption is questionable in many real-world environments. In the reality, nodes might need to communicate by means of an incomplete network, and Byzantine nodes might not forward messages. Furthermore, Byzantine nodes might not behave correctly and, for example, corrupt messages. Therefore, in order to truly understand Byzantine Agreement, we need both ingredients: asynchrony and incomplete communication networks. In this paper, we study the asynchronous Byzantine agreement problem in incomplete networks. A classic result by Danny Dolev proved that in a distributed system with n nodes in the presence of f Byzantine nodes, the vertex connectivity of the system communication graph should be at least (2f+1). While Dolev's result was for synchronous deterministic systems, we demonstrate that the same bound also holds for asynchronous randomized systems. We show that the bound is tight by presenting a randomized algorithm, and a matching lower bound.
