摘要：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.
