论文标题
拜占庭的共识为θ（n^2）：即使部分同步，dolev-reischuk结合也很紧！ [扩展版本]
Byzantine Consensus is Θ(n^2): The Dolev-Reischuk Bound is Tight even in Partial Synchrony! [Extended Version]
论文作者
论文摘要
Dolev-Reischuk Bound说，在最坏情况下，任何确定性的拜占庭共识方案都具有（至少）二次通信复杂性。虽然已经显示在同步环境中界限紧密，但尚不清楚是否可以通过部分同步获得具有二次通信复杂性的共识协议。到目前为止，部分同步设置中拜占庭共识的最有效的解决方案具有立方通信的复杂性（例如，HotStuff，二进制DBFT）。 本文通过引入小队来缩小现有差距，这是一种部分同步的拜占庭共识方案，具有二次最差的通信复杂性。此外，小队具有最佳弹性，并实现了线性最差的延迟延迟复杂性。基础小队的主要技术贡献在于我们求解视图同步的方式，即以足够长的时间将所有正确的流程带到相同观点的问题。具体而言，我们提出了raresync，这是一种具有二次通信复杂性和线性潜伏复杂性的视图同步协议，我们使用该协议来获得小队。
The Dolev-Reischuk bound says that any deterministic Byzantine consensus protocol has (at least) quadratic communication complexity in the worst case. While it has been shown that the bound is tight in synchronous environments, it is still unknown whether a consensus protocol with quadratic communication complexity can be obtained in partial synchrony. Until now, the most efficient known solutions for Byzantine consensus in partially synchronous settings had cubic communication complexity (e.g., HotStuff, binary DBFT). This paper closes the existing gap by introducing SQuad, a partially synchronous Byzantine consensus protocol with quadratic worst-case communication complexity. In addition, SQuad is optimally-resilient and achieves linear worst-case latency complexity. The key technical contribution underlying SQuad lies in the way we solve view synchronization, the problem of bringing all correct processes to the same view with a correct leader for sufficiently long. Concretely, we present RareSync, a view synchronization protocol with quadratic communication complexity and linear latency complexity, which we utilize in order to obtain SQuad.
