Paper 2019/886
Round Complexity of Byzantine Agreement, Revisited
T-H. Hubert Chan, Rafael Pass, and 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
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint. MINOR revision.
- Keywords
- byzantine agreementconsensus
- Contact author(s)
- runting @ gmail com
- History
- 2019-08-05: received
- Short URL
- https://ia.cr/2019/886
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2019/886, author = {T-H. Hubert Chan and Rafael Pass and Elaine Shi}, title = {Round Complexity of Byzantine Agreement, Revisited}, howpublished = {Cryptology {ePrint} Archive, Paper 2019/886}, year = {2019}, url = {https://eprint.iacr.org/2019/886} }