论文标题
寻找最佳身份验证的拜占庭协议
In Search for an Optimal Authenticated Byzantine Agreement
论文作者
论文摘要
在本文中，我们挑战了状态机器复制系统的常规方法，以在最终同步通信模型中设计确定性协议协议。我们首先证明，没有这种协议可以保证在全球稳定时间之前保证有限的沟通成本，并提出了一种希望获得最佳（同步）的方法，但为最糟糕的情况做准备（异步）。因此，我们设计了一种乐观的拜占庭协议协议协议，该协议首先尝试了一种有效的确定性算法，该算法仅依赖于同步终止，然后，只有在异步而没有达成协议时，该方案使用随机的异步方案来保证终止终止的后备方案，该方案具有可能性为1。 我们正式证明我们的协议在所有网络条件和故障场景下都实现了最佳的通信复杂性。我们首先证明了同步确定性拜占庭协议协议协议协议的$ω（ft+ t）$的下限，其中$ t $是故障阈值，而$ f $是实际失败的数量。然后，我们提出一个紧密的上限，并将其用于乐观协议的同步部分。最后，对于异步后备，我们使用（最佳）VABA协议的变体，我们将其重建以将其与同步部分安全地结合。 我们认为，我们对失败的适应性同步拜占庭协议协议具有独立的兴趣，因为这是我们知道哪种交流复杂性最佳地取决于实际失败数量的第一个协议。
In this paper, we challenge the conventional approach of state machine replication systems to design deterministic agreement protocols in the eventually synchronous communication model. We first prove that no such protocol can guarantee bounded communication cost before the global stabilization time and propose a different approach that hopes for the best (synchrony) but prepares for the worst (asynchrony). Accordingly, we design an optimistic byzantine agreement protocol that first tries an efficient deterministic algorithm that relies on synchrony for termination only, and then, only if an agreement was not reached due to asynchrony, the protocol uses a randomized asynchronous protocol for fallback that guarantees termination with probability 1. We formally prove that our protocol achieves optimal communication complexity under all network conditions and failure scenarios. We first prove a lower bound of $Ω(ft+ t)$ for synchronous deterministic byzantine agreement protocols, where $t$ is the failure threshold, and $f$ is the actual number of failures. Then, we present a tight upper bound and use it for the synchronous part of the optimistic protocol. Finally, for the asynchronous fallback, we use a variant of the (optimal) VABA protocol, which we reconstruct to safely combine it with the synchronous part. We believe that our adaptive to failures synchronous byzantine agreement protocol has an independent interest since it is the first protocol we are aware of which communication complexity optimally depends on the actual number of failures.
