Brief Announcement: Multi-Threshold Asynchronous Reliable Broadcast and Consensus

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

International Symposium on Distributed Computing — DISC 2020, Oct 2020.

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 \emph{multi-threshold} reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as $f \leq t_{v}$ , $f \leq t_{c}$ and $f \leq 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 $max {t_{c}, t_{v}} + 2 t_{t} < n$ .

-Multi-threshold almost-surely consensus is possible if $max {t_{c}, t_{v}} + 2 t_{t} < n$ , $2 t_{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}} + 2 t_{t} < n$ and $2 t_{v} + t_{t} < n$ .

-Multi-threshold $(1 - ϵ)$ -consensus is possible if and only if $max {t_{c}, t_{v}} + 2 t_{t} < n$ and $2 t_{v} + t_{t} < n$ .

BibTeX Citation

@inproceedings{HiKaLi20a,
    author       = {Martin Hirt and Ard Kastrati and Chen-Da Liu Zhang},
    title        = {Brief Announcement: Multi-Threshold Asynchronous Reliable Broadcast and Consensus},
    booktitle    = {International Symposium on Distributed Computing --- DISC 2020},
    year         = {2020},
    month        = {10},
}