Welcome to the resource topic for 2020/322
Title:
Optimal and Error-Free Multi-Valued Byzantine Consensus Through Parallel Execution
Authors: Andrew Loveless, Ronald Dreslinski, Baris Kasikci
Abstract:Multi-valued Byzantine Consensus (BC), in which n processes must reach agreement on a single L-bit value, is an essential primitive in the design of distributed cryptographic protocols and fault-tolerant distributed systems. One of the most desirable traits for a multi-valued BC protocol is to be error-free. In other words, have zero probability of producing incorrect results. The most efficient error-free multi-valued BC protocols are built as extension protocols, which reduce agreement on large values to agreement on small sequences of bits whose lengths are independent of L. The best extension protocols achieve \mathcal{O}(Ln) communication complexity, which is optimal, when L is large relative to n. Unfortunately, all known error-free and communication-optimal BC extension protocols require each process to broadcast at least n bits with a binary Byzantine Broadcast (BB) protocol. This design limits the scalability of these protocols to many processes, since when n is large, the binary broadcasts significantly inflate the overall number of bits communicated by the extension protocol. In this paper, we present Byzantine Consensus with Parallel Execution (BCPE), the first error-free and communication-optimal BC extension protocol in which each process only broadcasts a single bit with a binary BB protocol. BCPE is a synchronous and deterministic protocol, and tolerates f < n/3 faulty processes (the best resilience possible). Our evaluation shows that BCPE’s design makes it significantly more scalable than the best existing protocol by Ganesh and Patra. For 1,000 processes to agree on 2 MB of data, BCPE communicates 10.92\times fewer bits. For agreement on 10 MB of data, BCPE communicates 6.97\times fewer bits. BCPE also matches the best existing protocol in all other standard efficiency metrics.
ePrint: https://eprint.iacr.org/2020/322
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 .