Byzantine causal reliable broadcast with constant message overhead
Byzantine Causal Reliable Broadcast with Constant Metadata Overhead
Distributed, Parallel, and Cluster ComputingData Structures and Algorithms
Summary
Sending messages reliably in a system where some parts might behave badly is tricky, especially when messages need to follow a certain order. The authors improved how these messages are sent so the extra information attached to each message stays the same size, no matter how big the system grows. Their solution uses smarter steps to keep messages safe and ordered without making them bigger over time. This approach also reduces the total communication cost compared to earlier methods.
What this means in practice
- •For blockchain developers: Ensure ordered and reliable message delivery with minimal overhead in blockchain systems under adversarial conditions.
- •For social network engineers: Maintain causal message order efficiently in decentralized social platforms prone to faulty or malicious nodes.
Authors
Purv Patel, Ajay D. Kshemkalyani
Abstract
Asynchronous Byzantine Reliable Broadcast (BRB) is a fundamental primitive that guarantees agreement and validity in distributed systems subject to Byzantine faults, but it lacks ordering guarantees. Causal message ordering is important for many applications such as blockchain and social networking. Existing solutions for Byzantine Causal Reliable Broadcast (BCRB) have several drawbacks. Such protocols typically append vector clocks or dependency barriers to application messages, resulting in a metadata overhead that scales linearly with $n$, the number of processes in the system. In this paper, we propose the first optimal message overhead BCRB algorithm that guarantees safety. We do this by re-engineering Bracha's BRB algorithm with relatively small but critical modifications, and prove that our algorithm solves BCRB with optimal message metadata. The algorithm achieves constant-size $\mathcal{O}(1)$ message metadata overhead and $\mathcal{O}(n^2)$ messages, resulting in $\mathcal{O}(n^2)$ communication word complexity. This is as against $\mathcal{O}(n^3)$ communication word complexity of existing protocols. The algorithm tolerates $f < n/3$ Byzantine processes, which is the well-known optimal resilience bound, and uses four phases.