Basil: Breaking up BFT with ACID (transactions)
This work addresses the scalability bottleneck in BFT systems for distributed databases, offering a significant performance boost that is incremental but impactful for applications requiring Byzantine fault tolerance with transactions.
The paper tackles the problem of achieving high throughput in Byzantine Fault Tolerant (BFT) key-value stores by introducing Basil, the first transactional, leaderless BFT system that uses ACID transactions to enable parallel execution and single-round commits, resulting in a four to five times throughput improvement over traditional BFT systems and only a four times slowdown compared to non-Byzantine systems.
This paper presents Basil, the first transactional, leaderless Byzantine Fault Tolerant key-value store. Basil leverages ACID transactions to scalably implement the abstraction of a trusted shared log in the presence of Byzantine actors. Unlike traditional BFT approaches, Basil executes non-conflicting operations in parallel and commits transactions in a single round-trip during fault-free executions. Basil improves throughput over traditional BFT systems by four to five times, and is only four times slower than TAPIR, a non-Byzantine replicated system. Basil's novel recovery mechanism further minimizes the impact of failures: with 30% Byzantine clients, throughput drops by less than 25% in the worst-case.