Welcome to the resource topic for 2019/886
Title:
Round Complexity of Byzantine Agreement, Revisited
Authors: T-H. Hubert Chan, Rafael Pass, Elaine Shi
Abstract: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. First, although expected constant-round protocols are known in the honest majority setting, it is unclear whether one has to settle for expected constant-round or whether there exist better protocols that are worst-case constant-round. Second, for the corrupt majority setting, the existence of sublinear-round BA protocols continues to ellude us except for the narrow regime when only sublinearly more than a half are corrupt. In this paper, we make a couple important steps forward in bridging this gap. We show two main results: - No (even randomized) protocol that completes in worst-case o\left(\log(1/\delta)/\log \log(1/\delta)\right) rounds can achieve BA with 1-\delta probability, even when only 1% of the nodes are corrupt. In comparison, known expected constant-round, honest-majority protocols complete in O(\log(1/\delta)) rounds in the worst-case. Therefore, our lower bound is tight upto a \log\log factor for the honest majority setting. - There exists a corrupt-majority BA protocol that terminates in O(\log(1/\delta)/\epsilon) rounds in the worst case and tolerates (1-\epsilon) fraction of corrupt nodes. Our upper bound is optimal upto a logarithmic factor in light of the elegant \Omega(1/\epsilon) lower bound by Garay et al. (FOCS’07).
ePrint: https://eprint.iacr.org/2019/886
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .