Sublinear-Round Byzantine Agreement Under Corrupt Majority
Sublinear-Round Byzantine Agreement Under Corrupt Majority
复制标题
腐败多数下的次线性拜占庭协议
DOI：
10.1007/978-3-030-45388-6_9
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
E. Shi
中科院分区：
文献类型：
--
作者：
T;R. Pass;E. Shi
尽管拜占庭协议(BA)的研究已有三十年之久，或许有些令人惊讶的是，我们对其整体复杂性的理解仍存在很大差距。一个长期悬而未决的问题是：在腐败多数情况下，我们能否实现具有次线性轮数复杂性的BA？归功于Garay等人的美丽作品。(Focs‘07)和Fitzi and Nielsen(Disk’09)，我们对这个问题有了部分肯定的回答，尽管对于较窄的制度\(f=n/2+o(N)\)，其中f是被破坏的节点数，n是节点数。到目前为止，即使对于静态损坏，也没有关于设置\(f>；0.51n\)的积极结果！
Although Byzantine Agreement (BA) has been studied for three decades, perhaps somewhat surprisingly, there still exist significant gaps in our understanding regarding its round complexity. A long-standing open question is the following: can we achieve BA with sublinear round complexity under corrupt majority? Due to the beautiful works by Garay et al. (FOCS’07) and Fitzi and Nielsen (DISC’09), we have partial and affirmative answers to this question albeit for the narrow regime \(f = n/2 + o(n)\) where f is the number of corrupt nodes and n is the total number of nodes. So far, no positive result is known about the setting \(f > 0.51n\) even for static corruption!