A Checker Built Like a Compiler

Boomslang, and what changes when uncertainty gets a name

Until now, a new isolation-checking problem has meant a new checker. A different isolation level, a database that allows range queries, an application that writes the same value twice: each broke some assumption of the checker before it, and someone wrote another one. Boomslang, which appeared at ATC 2026, argues that a new problem should cost a module instead. There is also a video of my ATC talk.

The question underneath

An isolation checker answers one question. Given a trace of what clients sent to a database and what came back, does there exist an execution allowed by the promised isolation level that explains it? Readers of an earlier post will recognize the shape: it is the existential definition of correctness, in its oldest and most concrete form.

The question is hard because the trace leaves things out. It does not say in which order writes to a key were installed. If two transactions wrote the same value, it does not say which one a read saw. If a range query skipped a key, it does not say whether the key was never inserted or was deleted. Checking is NP-complete in general, and the uncertainty is where the search lives.

Earlier checkers, including Cobra, which I worked on, each handled this by assuming a piece of it away: written values are unique, or the database logs its version order. Each assumption made one checker fast and fit one family of workloads. Real applications break them all the time.

Superpositions

Boomslang’s idea is to stop assuming and give the uncertainty a name. A superposition is, in the paper’s words, “a set of mutually exclusive possibilities that could explain part of the trace.” An unknown version order is a superposition. So is an ambiguous read, a physical delete, and a key a range query skipped. Different sources of doubt become one kind of object.

A superposition is the “there exists” broken into small, local pieces. Instead of one global search for an execution, the checker holds many small choices, each exactly one of a few alternatives, and asks whether some combination of them leaves the dependency graph without a forbidden cycle.

Once uncertainty is a first-class object, the checker takes the shape of a compiler. A front end records each operation’s inputs and outputs at the client and parses the trace into a graph. Modules lower it into an intermediate representation of known edges and superpositions. Optimization passes prune alternatives that would close a cycle and order the search. A back end hands the rest to a SAT solver that understands acyclicity.

What the shape buys

An isolation level becomes a module. The paper implements eight of them, from read committed to strict serializability, each in under 370 lines. It also reimplements three earlier checkers inside the framework: Cobra, about 16,600 lines on its own, becomes 271. The checker found a new bug in TiDB and a cycle in PostgreSQL that involves range queries, which existing checkers cannot capture.

None of this changes the worst case. The problem is still NP-complete, the trace still has to include every relevant transaction, and a module is trusted to say what its isolation level means. A wrong module gives a confident wrong answer.

The reason I care about the shape goes back to the consistency-checking post. It ended with a guess: if systems become tailored, each with its own protocol and its own weakened guarantee, checkers will have to be tailored too, likely written by the same machines that write the systems. A checker is hard to generate. A 300-line module against a fixed IR is not, and it is short enough for a person to read. The structure has already survived one change of hands: a coding agent ported Boomslang to C.

One compiler, many levels

Isolation checking did not need a checker for every scenario. It needed one place where the doubt in a trace is written down, and small modules that say what each guarantee forbids. The search is still hard. What changed is the price of asking a new question: it used to be a paper, and now it is a module.

References