  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.
