Modern distributed systems involve a diverse set of participants—ranging from cloud providers to jurisdictions, organizations, and individuals—who need to share data without necessarily trusting one another. These systems must ensure data availability and integrity, even when parties have disjoint, selfish, or adversarial interests. Byzantine Fault Tolerant (BFT) protocols provide strong guarantees in such settings and, for example, underpin much of today’s blockchain infrastructure. However, existing BFT solutions often fall short, delivering poor performance and rigid, restrictive interfaces. This dissertation proposes a new approach to efficient data sharing in environments with distributed trust—one that combines the robustness of BFT protocols with the performance and flexibility of traditional databases. We challenge the conventional BFT architecture, which centers on constructing a shared, tamper-proof totally ordered log and layering transactions on top. Instead, we advocate building a partially ordered BFT datastore directly. In particular, we argue that BFT systems, like traditional databases, should guarantee only serializable executions—those equivalent in effect to some total order—thereby avoiding the overhead of explicit total ordering. We realize this approach through two systems: Basil and Pesto. Basil is a distributed BFT key-value store that integrates replication and transaction coordination into a single, low-latency architecture. It adopts a client-driven design, enabling parallel and independent transaction execution and improving robustness over traditional BFT protocols. To support richer application needs, Pesto extends Basil with a SQL-style query interface, allowing seamless integration with existing systems.