Database system with transactional commit protocol based on safe conjunction of majorities

Abstract

A database system with a transactional commit protocol based on a safe conjunction of majorities is disclosed. In various embodiments, a directed acyclic graph comprising, for each of a plurality of database transactions, data identi- fying the transaction, data indicatingone or more prior database transactions on which the database transaction depends, and data indicating whether the transaction has been committed is stored. A leading edge comprising a set of committed leaf nodes of the directed acyclic graph is determined. Data representing the leading edge is provided to a transaction coordinator configured to use the leading edge to determine based at least in part on the leading edge to commit a transaction.