  Atomic Commit Problem (ACP) is a single-shot agreement problem similar to
consensus, meant to model the properties of transaction commit protocols in
fault-prone distributed systems. We argue that ACP is too restrictive to
capture the complexities of modern transactional data stores, where commit
protocols are integrated with concurrency control, and their executions for
different transactions are interdependent. As an alternative, we introduce
Transaction Certification Service (TCS), a new formal problem that captures
safety guarantees of multi-shot transaction commit protocols with integrated
concurrency control. TCS is parameterized by a certification function that can
be instantiated to support common isolation levels, such as serializability and
snapshot isolation. We then derive a provably correct crash-resilient protocol
for implementing TCS through successive refinement. Our protocol achieves a
better time complexity than mainstream approaches that layer two-phase commit
on top of Paxos-style replication.
