MiniCast: Minimizing the Communication Complexity of Reliable Broadcast

ePrint Report: MiniCast: Minimizing the Communication Complexity of Reliable Broadcast

Thomas Locher, Victor Shoup

We give a new protocol for reliable broadcast with improved communication complexity for long messages. Namely, to reliably broadcast a message a message $m$ over an asynchronous network to a set of $n$ parties, of which fewer than $n/3$ may be corrupt, our protocol achieves a communication complexity of $1.5 |m| n + O( \kappa n^2 \log(n) )$, where $\kappa$ is the output length of a …

asynchronous broadcast communication complexity eprint report message messages network parties protocol report thomas