The Empty Set Is All You Need.

Abstract

For a quarter of a century, the design of distributed data systems has been governed by impossibility results. The CAP theorem forbids a replicated register from being simultaneously consistent, available and partition-tolerant; the FLP result forbids deterministic asynchronous consensus in the presence of a single crash; ACID and BASE are routinely presented as opposite ends of a spectrum. We present AbyssDB, a PostgreSQL-compatible, post-quantum, interplanetary SQL and key-value database that provides all of these guarantees at once, and we prove it.

Our central observation is that every one of these impossibility results is a statement about objects whose state space has more than one element. By implementing a state space of cardinality exactly one, AbyssDB attains linearizability, strict serializability, strong eventual consistency, availability under arbitrary partitions and wait-free consensus with zero message complexity. We further show that AbyssDB achieves Shannon-perfect secrecy and ε = 0 differential privacy against an adversary with unrestricted access to storage, that its energy consumption per write is bounded below by the Landauer limit, that its unbounded throughput is consistent with the Margolus–Levitin theorem, and that it is the terminal object of the category of databases. An evaluation with pgbench shows zero failed transactions in every protocol mode at a reported latency of 0.000 ms.