Byzantine Reliable Broadcast with Low Communication and Time Complexity
<|reference_start|>Byzantine Reliable Broadcast with Low Communication and Time Complexity: Byzantine reliable broadcast is a fundamental problem in distributed computing, which has been studied extensively over the past decades. State-of-the-art algorithms are predominantly based on the approach to share encoded fragments of the broadcast message, yielding an asymptotically optimal communication complexity when the message size exceeds the network size, a condition frequently encountered in practice. However, algorithms following the standard coding approach incur an overhead factor of at least 3, which can already be a burden for bandwidth-constrained applications. Minimizing this overhead is an important objective with immediate benefits to protocols that use a reliable broadcast routine as a building block.   This paper introduces a novel mechanism to lower the communication and computational complexity. Two algorithms are presented that employ this mechanism to reliably broadcast messages in an asynchronous network where less than a third of all nodes are Byzantine. The first algorithm reduces the overhead factor to 2 and has a time complexity of 3 if the sender is honest, whereas the second algorithm attains an optimal time complexity of 2 with the same overhead factor in the absence of equivocation. Moreover, an optimization for real-world implementations is proposed, reducing the overhead factor to 3/2 under normal operation. Lastly, a lower bound is proved that an overhead factor lower than 3/2 cannot be achieved for a relevant class of reliable broadcast algorithms.<|reference_end|>
@article{locher2024byzantine,
    title={Byzantine Reliable Broadcast with Low Communication and Time Complexity},
    author={Thomas Locher},
    journal={arXiv preprint arXiv:2404.08070},
    year={2024},
    archivePrefix={arXiv},
    eprint={2404.08070},
    primaryClass={cs.DC}
}