2026-07-27T03:51:48Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:19519 2024-03-06T11:04:12Z ddc:004 open_access

On the Round Complexity of Asynchronous Crusader Agreement Abraham, Ittai Ben-David, Naama Stern, Gilad Yandamuri, Sravya lower bounds asynchronous protocols round complexity 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ittai Abraham and Naama Ben-David and Gilad Stern and Sravya Yandamuri 2024 Is Part Of LIPIcs, Volume 286, 27th International Conference on Principles of Distributed Systems (OPODIS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2023.29 urn:nbn:de:0030-drops-195195 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2023.29 eng https://creativecommons.org/licenses/by/4.0/legalcode