[Resource Topic] 2023/1586: On the Round Complexity of Asynchronous Crusader Agreement

Welcome to the resource topic for 2023/1586

On the Round Complexity of Asynchronous Crusader Agreement

Authors: Ittai Abraham, Naama Ben-David, Gilad Stern, Sravya Yandamuri


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.

ePrint: https://eprint.iacr.org/2023/1586

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 .