Paper 2020/958

Multi-Threshold Asynchronous Reliable Broadcast and Consensus

Martin Hirt, Ard Kastrati, and Chen-Da Liu-Zhang

Abstract

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\le t_v$, $f\le t_c$ and $f\le t_t$ respectively. For consensus, we consider both variants of $(1-ϵ)$-consensus and \emph{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 $$. -Multi-threshold almost-surely consensus is possible if $$, $$ and $$. Assuming a global coin, it is possible if and only if $$ and $$. -Multi-threshold $$-consensus is possible if and only if $$ and $$.