MiniCast: Minimizing the communication complexity of reliable broadcast with Victor Shoup

Reliable broadcast in asynchronous networks ensures all honest parties receive identical messages despite adversarial behavior, even when the sender is corrupt 0:52. The protocol uses echo and vote mechanisms to guarantee correctness and liveness via many Echoes and unique votes properties 1:45. Eraser codes—specifically Reed-Solomon-based—reduce communication complexity from $O(n^2)$ to $O(Mn)$ by encoding messages into fragments and using Merkle trees for verification, with optimizations cutting the constant factor from 3 to 1.5 via two-level encoding and post-facto consistency guards 9:55.

Key Takeaways:
• Reliable broadcast ensures message consistency in adversarial asynchronous networks 0:52.
• Classic protocol uses echo and vote mechanisms with many Echoes and quorum intersection to ensure correctness and liveness 1:45.
• Eraser codes reduce communication complexity from $O(n^2)$ to $O(Mn)$ via fragment encoding and Merkle tree verification 9:55.
• A two-level encoding scheme with mini-fragments and a post-facto guard reduces the constant factor to 1.5, improving efficiency without sacrificing correctness 14:30.

This approach is practical, with encoding/decoding times (milliseconds) negligible compared to network transmission delays, making it viable for real-world systems like leader-based consensus protocols.

Sources:

• 0:52 Introduction to reliable broadcast and adversarial conditions.
• 1:45 Classic broadcast protocol mechanics and key properties.