Fast Byzantine Total Order Broadcast

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 e 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.