Welcome to the resource topic for 2020/958
Title:
Multi-Threshold Asynchronous Reliable Broadcast and Consensus
Authors: Martin Hirt, Ard Kastrati, 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-\epsilon)-consensus and \emph{almost-surely terminating} consensus, where termination is guaranteed with probability (1-\epsilon) 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-\epsilon)-consensus is possible if and only if \max\{t_c, t_v\} + 2t_t < n and 2t_v + t_t < n.
ePrint: https://eprint.iacr.org/2020/958
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .