Robust and High-Performance Wide-Area Consensus Protocols
Pasindu Nivanthaka Tennage
Ph.D. thesis advised by Bryan Ford
August 15, 2025
Abstract:
Deploying consensus protocols in the wide-area is challenging due to
unpredictable and adversarial nature of wide-area networks. This thesis
explores five critical challenges that affect the operation of consensus
protocols in the wide-area networks; (1) performance vulnerability of
leader-based protocols to leader-targeted attacks, (2) losing liveness under
adversarial network conditions, (3) throughput bottlenecks caused by leader
overload, (4) recovery time versus liveness trade-off caused by sub-optimal
manually configured timeouts, and (5) high commit latency in DAG-based
asynchronous byzantine fault tolerant protocols.
To address these five challenges, this thesis proposes five novel protocols
spread across four chapters. We first propose Baxos, a novel extension of
the Paxos protocol, which replaces the traditional leader election in
Multi-Paxos with a novel Random Exponential Backoff scheme. Baxos enables all
nodes to propose, while handling contention using random exponential backoff,
and enhances resilience against leader-targeted attacks. Second, we propose
SADL-RACS, a novel modular state machine replication protocol. SADL-RACS
overcomes the challenges of network asynchrony and leader performance
bottleneck. RACS is a novel randomized crash fault-tolerant consensus
protocol that guarantees liveness under network asynchrony. SADL eliminates
the leader bottleneck by decoupling request dissemination from the critical
path, distributing the load evenly across participating nodes. Third, we
present QuePaxa, a novel randomized consensus algorithm that replaces
manually configured timeouts in leader-based protocols with adaptive hedging
delays. QuePaxa reduces recovery time during replica crashes or intermittent
slowdowns while improving liveness under adversarial network conditions.
Finally, we present Mahi-Mahi, a novel asynchronous DAG-based BFT protocol
that achieves high throughput with sub-second commit latency. Unlike the
certified DAG-based protocols, Mahi-Mahi employs an uncertified DAG to commit
blocks, significantly reducing the number of network hops required per
commitment.
Through protocol design, security proofs, prototype implementation, and
extensive evaluation, this thesis demonstrates that each proposed solution
delivers substantial improvements in performance and robustness. First, we show
that Baxos improves throughput by up to 128% under leader-targeted attacks
compared to Multi-Paxos and Raft. Second, we show that SADL-RACS ensures
liveness under adversarial network conditions by providing a throughput of
196,000 requests per second. Third, we demonstrate that QuePaxa significantly
outperforms the existing leader-based protocols under adversarial network
conditions, achieving at least 75,000 requests per second with a median latency
of 380ms in wide-area deployments, while maintaining low recovery time, despite
the choice of timeout value. Finally, Mahi-Mahi achieves over 100,000
transactions per second with sub-second average latency in wide-area
deployments, setting a new milestone in asynchronous BFT protocol performance.
These contributions transform high-performance wide-area consensus from a
theoretical concept into a practical reality.