Fast Byzantine Total Order Broadcast

Abstract

This paper presents Flutter, the first Byzantine Total Order Broadcast implementation with a broadcast-to-delivery latency of $2\hat{I}”+\hat{I}\mu$ time units, $\hat{I}”$ being the message delay and $\hat{I}\mu$ 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\hat{I}”$ 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 $\hat{I}”$ time units when all correct servers propose the same value.

This document is the full version of the PODC 2026 paper with DOI https://doi.org/10.1145/3796701.3815946