Optimizing reliable broadcast latency with improved step guarantees
Optimistic Reliable Broadcast in Three Steps
Distributed, Parallel, and Cluster Computing
Summary
Reliable broadcast is a way for many computers to agree on a message even if some are faulty or malicious. The paper studies how to speed up this process when the broadcaster is honest and faults are limited. The authors present new methods that reduce the number of steps needed in optimistic cases while preserving fault tolerance. They also prove that their improvements are the best possible under certain conditions.
What this means in practice
- •For blockchain developers: Build faster consensus protocols that guarantee quick message delivery even with some faulty or malicious nodes.
- •For distributed database engineers: Improve data replication algorithms to reduce latency while maintaining consistency in unreliable network environments.
Authors
Nikita Polyanskii
Abstract
We study the latency tradeoffs of signature-free asynchronous reliable broadcast with optimistic two-step delivery. We consider $n$ parties, of which at most $f$ are Byzantine. An optimistic fault budget $b\le f$ guarantees two-step delivery with an honest broadcaster and at most $b$ faults, while correctness tolerates $f$ faults. We write $(d_o,d_s,d_t)$ for optimistic latency, honest-broadcaster latency with up to $f$ faults, and totality delay-the elapsed time from first to last honest delivery. For $3f+1\le n<4f$, our first construction improves Opt-RBC's $(2,4,4)$ guarantees to $(2,3,4)$, preserving its maximal optimistic budget $b_*=\lfloor n/2\rfloor-f$. Thus maximal optimism is compatible with the optimal three-step good case. We prove a complementary lower bound: for $3f+1\le n<4f$, every deterministic reliable broadcast protocol in our asynchronous model with two-step optimistic budget $b\ge n-3f$ has totality delay at least three, even when the broadcaster is honest. Our second construction achieves $(2,3,3)$, matching this lower bound at maximal optimism when $f\ge2$ and $\lceil(10f-3)/3\rceil\le n<4f$. Both constructions use quadratic messages and tolerate adaptive corruption. In the matching range, maximal optimism therefore costs exactly one totality step relative to Bracha's $(3,3,2)$, without increasing good-case latency.