Abstract
As Byzantine Fault Tolerant (BFT) protocols are increasingly adopted for user-facing applications such as payments and smart contracts, it is crucial that they provide low latency. To reduce latency, some BFT consensus protocols use a leaderless, speculative, fast path where clients broadcast requests directly to replicas, enabling end-to-end commit latency of two message delays (). However, such a fast path is extremely fragile: concurrent requests can cause replicas to diverge when they receive requests in different orders, triggering costly recovery procedures. This paper presents Aspen, a leaderless speculative BFT protocol that handles concurrent requests while achieving near-optimal latency of . The term is a short waiting delay introduced by Aspen's best effort ordering layer, which uses loosely synchronized clocks and network delay estimates to provide a tentative order. To make its fast path even more robust to intermittent divergence, Aspen adds extra replicas () as well as novel recovery mechanisms that allow the system to tolerate divergence while preserving safety and performance. In experiments with geo-distributed replicas, Aspen reduces the median latency of requests by -- compared to state-of-the-art BFT protocols, while sustaining up to the peak throughput of throughput-optimized designs.