Fast Byzantine Total Order Broadcast
For distributed systems requiring fast and secure broadcast, Flutter reduces latency by nearly one message delay compared to prior protocols, offering a quasi-optimal solution.
Flutter achieves Byzantine Total Order Broadcast with a broadcast-to-delivery latency of 2Δ+ε, improving over the state-of-the-art 3Δ, and is proven quasi-optimal. It is deterministic, leaderless, and signature-free, requiring 5f+1 servers under partial synchrony.
This paper presents Flutter, the first Byzantine Total Order Broadcast implementation with a broadcast-to-delivery latency of $2Δ+ ε$ time units, $Δ$ being the message delay and $ε$ an arbitrarily small constant margin, when all processes are correct, the network is synchronous, hence local clocks are well-synchronized. Under the same conditions, state-of-the-art protocols require at least $3Δ$ time units in practical deployments where clients differ from servers. We prove Flutter's good-case latency is quasi-optimal, meaning it cannot be improved upon by any finite amount. Flutter is deterministic, leaderless, and signature-free hence quantum-resilient; it assumes partial synchrony and at least $5f + 1$ servers, where $f$ bounds the number of faults. Under the hood, Flutter builds upon Blink, a novel Binary Consensus implementation with Representative Validity, whose fast path enables decisions in $Δ$ time units when all correct servers propose the same value.