论文标题
预期线性圆形同步：线性拜占庭SMR的缺失链接
Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR
论文作者
论文摘要
状态机器复制（SMR）解决方案通常将时间分为回合，每回合都有指定的领导者驾驶决策。一旦所有正确的流程都同步到同一轮，就可以保证进度，而该回合的领导者是正确的。最近，一旦发生这种圆形同步，最近建议的拜占庭SMR解决方案，例如HotStuff，Tendermint和Librabft，通过线性消息复杂性和恒定的时间复杂性实现了进步。但是，圆形同步本身会增加额外的成本。通过Dolev和Reischuk的下限，任何确定性解决方案都必须具有$ω（n^2）$通信复杂性。然而，随机圆形同步具有预期线性消息复杂性的问题仍然开放。 我们提出了一种算法，该算法首次实现了与预期线性消息复杂性和预期恒定延迟的圆形同步。现有协议可以使用我们的圆形同步算法以相同的渐近性能求解拜占庭SMR。
State Machine Replication (SMR) solutions often divide time into rounds, with a designated leader driving decisions in each round. Progress is guaranteed once all correct processes synchronize to the same round, and the leader of that round is correct. Recently suggested Byzantine SMR solutions such as HotStuff, Tendermint, and LibraBFT achieve progress with a linear message complexity and a constant time complexity once such round synchronization occurs. But round synchronization itself incurs an additional cost. By Dolev and Reischuk's lower bound, any deterministic solution must have $Ω(n^2)$ communication complexity. Yet the question of randomized round synchronization with an expected linear message complexity remained open. We present an algorithm that, for the first time, achieves round synchronization with expected linear message complexity and expected constant latency. Existing protocols can use our round synchronization algorithm to solve Byzantine SMR with the same asymptotic performance.
