Paper 2023/1586
On the Round Complexity of Asynchronous Crusader Agreement
Abstract
We present new lower and upper bounds on the number of communication rounds required for asynchronous Crusader Agreement (CA) and Binding Crusader Agreement (BCA), two primitives that are used for solving binary consensus. We show results for the information theoretic and authenticated settings. In doing so, we present a generic model for proving round complexity lower bounds in the asynchronous setting. In some settings, our attempts to prove lower bounds on round complexity fail. Instead, we show new, tight, rather surprising round complexity upper bounds for Byzantine fault tolerant BCA with and without a PKI setup.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Preprint.
- Keywords
- lower boundsasynchronousbyzantineagreement
- Contact author(s)
-
ittai abraham @ intel com
naamabd14 @ gmail com
gilad stern @ mail huji ac il
Sravya yandamuri @ duke edu - History
- 2023-10-13: approved
- 2023-10-13: received
- See all versions
- Short URL
- https://ia.cr/2023/1586
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2023/1586,
author = {Ittai Abraham and Naama Ben-David and Gilad Stern and Sravya Yandamuri},
title = {On the Round Complexity of Asynchronous Crusader Agreement},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/1586},
year = {2023},
url = {https://eprint.iacr.org/2023/1586}
}
