2026-07-20T14:36:29Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13491 2024-03-06T10:52:11Z ddc:004 open_access

Multi-Threshold Asynchronous Reliable Broadcast and Consensus Hirt, Martin Kastrati, Ard Liu-Zhang, Chen-Da broadcast byzantine agreement multi-threshold Classical protocols for reliable broadcast and consensus provide security guarantees as long as the number of corrupted parties f is bounded by a single given threshold t. If f > t, these protocols are completely deemed insecure. We consider the relaxed notion of multi-threshold reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as f ≤ t_v, f ≤ t_c and f ≤ t_t respectively. For consensus, we consider both variants of (1-ε)-consensus and almost-surely terminating consensus, where termination is guaranteed with probability (1-ε) and 1, respectively. We give a very complete characterization for these primitives in the asynchronous setting and with no signatures: - Multi-threshold reliable broadcast is possible if and only if max{t_c,t_v} + 2t_t < n. - Multi-threshold almost-surely consensus is possible if max{t_c, t_v} + 2t_t < n, 2t_v + t_t < n and t_t < n/3. Assuming a global coin, it is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n. - Multi-threshold (1-ε)-consensus is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Hirt and Ard Kastrati and Chen-Da Liu-Zhang 2021 Is Part Of LIPIcs, Volume 184, 24th International Conference on Principles of Distributed Systems (OPODIS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2020.6 urn:nbn:de:0030-drops-134917 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2020.6 eng https://creativecommons.org/licenses/by/3.0/legalcode