2026-07-20T14:44:05Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11319 2024-03-06T10:47:56Z ddc:004 open_access

On the Round Complexity of Randomized Byzantine Agreement Cohen, Ran Haitner, Iftach Makriyannis, Nikolaos Orland, Matan Samorodnitsky, Alex Byzantine agreement lower bound round complexity We prove lower bounds on the round complexity of randomized Byzantine agreement (BA) protocols, bounding the halting probability of such protocols after one and two rounds. In particular, we prove that: 1) BA protocols resilient against n/3 [resp., n/4] corruptions terminate (under attack) at the end of the first round with probability at most o(1) [resp., 1/2+ o(1)]. 2) BA protocols resilient against n/4 corruptions terminate at the end of the second round with probability at most 1-Theta(1). 3) For a large class of protocols (including all BA protocols used in practice) and under a plausible combinatorial conjecture, BA protocols resilient against n/3 [resp., n/4] corruptions terminate at the end of the second round with probability at most o(1) [resp., 1/2 + o(1)]. The above bounds hold even when the parties use a trusted setup phase, e.g., a public-key infrastructure (PKI). The third bound essentially matches the recent protocol of Micali (ITCS'17) that tolerates up to n/3 corruptions and terminates at the end of the third round with constant probability. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Ran Cohen and Iftach Haitner and Nikolaos Makriyannis and Matan Orland and Alex Samorodnitsky 2019 Is Part Of LIPIcs, Volume 146, 33rd International Symposium on Distributed Computing (DISC 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2019.12 urn:nbn:de:0030-drops-113199 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2019.12 eng https://creativecommons.org/licenses/by/3.0/legalcode