文章基本信息

标题：Expected Linear Round Synchronization: The Missing Link for Linear Byzantine SMR
本地全文：下载
作者：Oded Naor ; Idit Keidar
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：179
页码：1-17
DOI：10.4230/LIPIcs.DISC.2020.26
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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Â²) 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.
关键词：Distributed Systems; State Machine Replication