  Traditional Byzantine Fault Tolerance (BFT) state machine replication
protocols assume a partial synchrony model, leading to a design where a leader
replica drives the protocol and is replaced after a timeout. Recently, we
witnessed a surge of asynchronous BFT protocols that use randomization to
remove the assumptions of bounds on message delivery times, making them more
resilient to adverse network conditions. However, these protocols still fall
short of being practical across a broad range of scenarios due to their cubic
communication costs, use of expensive primitives, and overall protocol
complexity. In this paper, we present Alea-BFT, the first asynchronous BFT
protocol to achieve quadratic communication complexity, allowing it to scale to
large networks. Alea-BFT brings the key design insight from classical protocols
of concentrating part of the work on a single designated replica, and
incorporates this principle in a two stage pipelined design, with an efficient
broadcast led by the designated replica followed by an inexpensive binary
agreement. We evaluated our prototype implementation across 10 sites in 4
continents, and our results show significant scalability gains from the
proposed design.
