Open Collections

Abstract

Multi-Byzantine Fault Tolerant (Multi-BFT) consensus enhances the scalability of traditional BFT protocols by allowing multiple consensus instances to run in parallel, thereby mitigating the leader bottleneck. However, existing Multi-BFT designs are fundamentally constrained by their reliance on global ordering across instances, which introduces latency, limits concurrency, and makes performance highly sensitive to straggler replicas. This dissertation presents three complementary systems—Ladon, Orthrus, and Hydra—that rethink ordering in Multi-BFT consensus to enable scalable, efficient, and secure transaction processing. Ladon addresses the inefficiencies caused by fixed global indices by proposing a dynamic global ordering protocol. It assigns monotonic ranks to blocks based on their generation time and pipelines rank coordination with consensus to minimize latency and protocol overhead, allowing the system to make progress independent of straggling instances. Orthrus introduces a hybrid ordering model that accelerates transaction confirmation through partial ordering while preserving global ordering for transactions with strict dependency requirements. It leverages a transaction partitioning strategy to maximize concurrency and employs an escrow mechanism to ensure atomicity across instances. Hydra further generalizes this approach by eliminating global ordering altogether. It adopts an object-centric architecture, decomposes transactions into dependency-aware Directed Acyclic Graphs (DAGs), and assigns them to instances based on object access. This design enables safe, parallel consensus without global ordering across instances. Together, these systems form a new ordering paradigm for Multi-BFT consensus. Through formal analysis and extensive evaluation, they demonstrate significant improvements in throughput and latency, laying the groundwork for the next generation of decentralized infrastructure.