CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis

Hünkar Can Tunç, Ameya Prashant Deshmukh, Berk Çirisci, Constantin Enea and Andreas Pavlogiannis

Nearly every tool that hunts for concurrency bugs — data races, deadlocks, atomicity violations — keeps a running happens-before order of a program's events, and for decades the go-to structure was the vector clock; but vector clocks choke on analyses that add orderings in the middle of a trace and cannot undo an ordering at all, forcing an expensive recompute whenever the analysis backtracks; this award-winning work from Aarhus and collaborators builds CSSTs, a data structure that inserts, deletes, and queries orderings in logarithmic time by reducing the problem to classic segment trees, making it the best structure for the whole family of non-streaming concurrency analyses.

The argument in one glance

Problem

Concurrency-bug hunters must maintain a happens-before order fast

Tools that look for data races, deadlocks, atomicity violations, and the like work by watching a program execute and reasoning about the order of its events. At the core of nearly every such analysis is a partial order — a happens-before relation over the events of the trace — that the analysis constantly grows, questions, and sometimes shrinks. Since a trace can hold billions of events, the cost of each ordering operation decides whether the whole analysis is usable.
What people did

Summarize the order with a vector clock

For decades the standard structure has been the vector clock: it exploits that a trace has only a handful of threads, so everything that happens-before an event can be summarized as one small integer array with an entry per thread. This replaces a factor of the trace length with the much smaller thread count, and for streaming analyses — where every new ordering ends at the event currently being processed — updates become very cheap.
Why it fell short

Vector clocks cannot handle mid-trace inserts or any deletion

Many analyses are not streaming: they insert orderings between arbitrary, already-processed events, and such an ordering must be propagated across the whole trace, restoring the expensive linear-in-the-trace cost. Worse, vector clocks cannot delete an ordering at all — so when an analysis tries a possibility, discovers a contradiction, and must backtrack, it has to recompute the entire partial order from scratch, at quadratic cost. Plain graphs allow deletion but cost quadratic time to keep transitively closed.
This paper's idea

Reduce reachability to suffix minima on sparse segment trees

CSSTs maintain the partial order by reducing the question "does this event reach that one" to a classic algorithmic problem, dynamic suffix minima, solved by segment trees. Inserting, deleting, and querying an ordering all run in roughly logarithmic time, and a sparse tree representation makes them faster still when cross-thread orderings are few. Where vector clocks are the best structure for streaming analyses, CSSTs are the best for non-streaming ones — and unlike vector clocks, they delete orderings cheaply, so backtracking analyses fly.

Why this problem is worth solving

The reason one data structure cannot serve every analysis is that analyses differ in a way that changes everything about the cost.

A dynamic analysis maintains a happens-before order and repeatedly inserts new orderings, asks reachability questions, and sometimes deletes orderings. What matters for performance is where the new orderings land. In a streaming analysis, events are processed one by one and every new ordering ends at the event being processed right now, at the frontier of the trace. Because that event has no successors yet, the ordering never has to be propagated anywhere, so a vector clock can absorb it in time proportional only to the thread count — essentially free. Data-race, deadlock, and atomicity checkers of this kind are exactly where vector clocks shine, and for them they are the best structure known. A non-streaming analysis is different: as it works, it inserts orderings between arbitrary events buried in the middle of the trace. Consistency checking is the canonical example — it guesses which write a read observed, and to respect that guess it must add saturation orderings deep inside the trace. Now the ordering has many successors, and propagating it through them costs time proportional to the whole trace length, even with vector clocks. The update pattern, not the analysis name, decides the cost, and it is the non-streaming analyses that had no good structure.

But the deeper pain, and the one vector clocks cannot touch at all, is undoing an ordering.

Many of the most powerful concurrency analyses work by search: they try a possibility — say, that a particular read observed a particular write — follow its consequences, and check whether the result is self-consistent. Often it is not: the guess induces a cycle, meaning an event would have to happen before itself, which is impossible. The analysis must then reject that guess, remove all the orderings it added, and try the next possibility. This is deletion, and it is where vector clocks fail completely. A vector clock is a compressed, transitively-closed summary of everything that happens-before an event; there is no efficient way to retract a single ordering from it, because you cannot tell which parts of the summary depended on the ordering being removed. In practice the only recourse is to throw the whole thing away and rebuild it, at cost quadratic in the trace. So a backtracking analysis, which may explore and abandon many possibilities, pays this enormous price over and over. A structure that could delete an ordering as cheaply as it inserts one would change what such analyses can afford to explore — and that is precisely the gap CSSTs fill.

What people did before, and where it broke

Plain reachability graph. Represent the partial order as a graph and answer “does one event reach another” directly. Where it broke. Keeping the graph transitively closed after every insertion or deletion costs time quadratic in the trace, which is hopeless when traces reach billions of events.
Vector clocks (the standard). Summarize each event’s entire happens-before set as one integer array with an entry per thread, shrinking a trace-length factor to a thread-count factor. Where it broke. This is only cheap for streaming updates at the frontier of the trace; an ordering inserted mid-trace must be propagated across the whole trace, and an ordering can never be deleted, so backtracking forces a full quadratic rebuild.
Segment-tree structure of the M2 race detector. A prior data structure used segment trees to make one specific race detector’s incremental reachability faster. Where it broke. It handled only insertion, not deletion, was not optimized for the sparsity of real traces, and was tied to that single analysis rather than being a general structure.
The gap. No structure served the whole family of non-streaming analyses well: something that inserts orderings anywhere in the trace, deletes them just as cheaply so search can backtrack, and answers reachability — all in far less than linear time, and getting faster when cross-thread orderings are sparse. That general, deletion-capable, sparsity-aware structure is what CSSTs provide.

How CSSTs work

From a happens-before order to logarithmic-time reachability

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Pay for the small dimension, not the large one. A trace has billions of events but only a handful of threads, and its happens-before order is just those few per-thread chains laced together with a sparse scattering of cross-thread orderings. CSSTs build everything around that asymmetry: costs are keyed to the tiny thread count and the sparse cross-chain edges, while the huge event count enters only through a logarithm. Designing so that the expense tracks the small, concentrated part of the problem rather than its bulk is the same move the low-bit language-model serving work covered elsewhere on this site makes, keying its cost to the small cluster of hard outlier values instead of paying full precision across every value in the tensor.

Swap the substrate underneath the analysis without changing the analysis. CSSTs are not a new bug-finding technique; they are a drop-in replacement for the vector clock or graph that an existing analysis already uses to store its happens-before order. Plug them in and the analysis computes exactly what it did before, only far faster and able to backtrack. Making an entire class of analyses scale by replacing the data structure they stand on, rather than rewriting their logic, is exactly the strategy the sanitizer shadow-memory work covered elsewhere on this site follows, speeding a whole family of memory-bug detectors by rebuilding the metadata structure beneath them while leaving the detection itself untouched.

Separate the two dimensions so each is handled on its own terms. The trace length and the thread count are different axes with different costs, and CSSTs refuse to let them tangle: the length axis is dispatched by a segment tree in logarithmic time, and the width axis by a small transitive closure that is cubic only in the tiny thread count. Neither dimension inflates the other, so an operation never pays the product of the two the way a naive graph does. Pulling apart two entangled quantities so each can be bounded independently is the same discipline the resize-scheduling work covered elsewhere on this site applies, separating the axes it must control so that bounding one never blows up the other.

Following a consistency check through a CSST

Trying and undoing a reads-from guess

Tracing a consistency check shows why cheap deletion is the whole game.

Step 1 of 5

Guess which write a read observed

A consistency analysis reaches a read event and must decide which earlier write supplied its value. It picks one candidate write and, to respect that choice, inserts the direct ordering plus the extra saturation orderings the choice forces deep inside the trace.

These orderings land between arbitrary mid-trace events, not at the frontier, so this is a non-streaming update.

Why it works

The order’s width is tiny. A trace has only a handful of threads → so its happens-before order is a few per-thread chains and reachability only ever crosses between them → so every cost keys to the small thread count and a logarithm of the trace, never the trace length itself.
Reachability becomes suffix minima. Storing each node’s earliest reach into every other chain → turns “does this event reach that one” into a single minimum-over-a-suffix lookup → so a decades-old segment tree answers and updates it in logarithmic time with no bespoke machinery.
A per-slot heap makes deletion cheap. Each node keeps all its cross-chain edges in a small min-heap → so removing an ordering is just a heap pop that refreshes the stored minimum → so a backtracking analysis undoes an ordering in logarithmic time instead of rebuilding the order at quadratic cost.
Sparsity shrinks the tree. Cross-thread orderings are rare in real traces → so most segment-tree entries are empty and can be dropped while suffix queries skip the missing parts → so both updates and queries get faster the sparser the trace, and the memory footprint falls too.
The two dimensions never multiply. Queries close reachability transitively across only the few chains → so the cross-chain step is cubic in the thread count rather than touching all the events → so a query stays cheap even when a path hops through several threads on its way.

What it costs (trade-offs and scope)

Vector clocks still win for streaming analyses. When every new ordering lands at the trace frontier and barely propagates, a vector-clock update is effectively constant time and beats a CSST’s logarithmic factor — in the C11 data-race analysis, where updates rarely propagate, vector clocks are faster, so CSSTs are the right tool for non-streaming, not streaming, analyses.
A single query is slightly slower than a vector-clock lookup. A vector-clock reachability check is one array read, while a CSST query walks a tree and closes reachability across chains, so per query it is a touch slower — CSSTs win overall only because insertion and deletion dominate in the non-streaming setting.
The query cost grows with the thread count. The cross-chain transitive closure is cubic in the number of chains, negligible when threads are few but not free as thread counts climb.
The advantage depends on sparsity. Worst-case memory is still proportional to trace length times thread count, the same as vector clocks; the practical time and memory savings come from low cross-thread density, so on dense partial orders the edge narrows.
It is a data structure, not a new analysis. CSSTs accelerate existing analyses as a drop-in replacement without changing what they compute or how precise they are; the contribution is scalability, and because some tools were not public the authors reimplemented them from their papers.
The sweet spot is width far below length. The gains are largest when threads are orders of magnitude fewer than events and cross-thread orderings are sparse — typical of real concurrency, but not guaranteed everywhere, since weak-memory models, for instance, raise the effective width.

The evaluation

Three ways to maintain a happens-before order

Property	Vector clocks	Plain graph	CSSTs
Insert an ordering mid-trace		Quadratic (transitive closure)
Delete an ordering		Supported, but slow
Reachability query		Direct, but structure is costly	Suffix lookup plus small closure
Best-suited analyses	Streaming	Tiny traces only

Three ways to maintain a happens-before partial order, evaluated across seven dynamic concurrency analyses from the literature — race, deadlock, memory-bug, use-after-free, consistency, C11-race, and linearizability analyses. CSSTs outperform vector clocks and segment trees in nearly all cases in both time and memory, handling benchmarks where vector clocks time out and prior structures run out of memory, and running orders of magnitude faster than plain graphs on the fully dynamic linearizability analysis that requires deletion — the exception being C11 race detection, where updates barely propagate and constant-time vector-clock lookups win.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

CSSTs are a clean, award-winning contribution: a general data structure that gives the whole family of non-streaming concurrency analyses what vector clocks gave streaming ones — cheap ordering operations — plus the deletion that vector clocks never had, all by reducing reachability to the textbook suffix-minima problem and exploiting the sparsity of real traces. Across seven analyses from the literature they win in nearly every case in both time and memory, and on the fully dynamic linearizability analysis they run orders of magnitude faster than the plain graphs it had to use. Read the result with its scope. This is a scalability tool, not a new analysis: it changes how fast an analysis runs, never what it computes or how precise it is. It does not dominate everywhere — for genuinely streaming analyses whose updates barely propagate, a vector clock’s constant-time update still wins, as the C11 race-detection case shows. A single reachability query is marginally slower than a vector-clock lookup, and the query has a cost cubic in the thread count; the memory edge and much of the speed edge rest on cross-thread orderings actually being sparse, which is typical but not universal. The durable lesson is that the right data structure, chosen by reducing a domain problem to a classic algorithmic primitive and exploiting the structure real inputs happen to have, can decide whether an entire class of analyses is feasible at scale.

Background

Why the data structure decides what analysis is possible

It helps to place CSSTs in the larger effort to make reasoning about tricky programs actually run at scale. Concurrent programs are hard to get right because their nondeterministic interleavings hide bugs that only some schedules expose, and the analyses that hunt those bugs are only as practical as the bookkeeping underneath them — which is why a better structure for the happens-before order is not a footnote but the thing that decides how large a program, or how deep a search, an analysis can afford. The nondeterministic-quantum-program correctness work covered elsewhere on this site sits on the same frontier from the verification side, building the formal machinery needed to reason soundly about programs whose behavior is not fixed by their input, where again the enabling substrate is what makes correctness reasoning tractable at all. The broad lesson across both is that progress in program correctness is often gated less by the high-level idea of an analysis than by the low-level representations and algorithms that let it scale — get the substrate right, by reducing to well-understood primitives and exploiting the structure real programs have, and analyses that were previously out of reach become routine.

If you remember only three things

1. Almost every dynamic concurrency analysis — for data races, deadlocks, atomicity violations, consistency, use-after-free, linearizability — maintains a happens-before partial order over a trace's events, repeatedly inserting orderings, querying reachability, and sometimes deleting orderings to backtrack. Traces hold up to billions of events, so the cost per operation decides scalability. Vector clocks, the decades-old standard, summarize each event's happens-before set as a per-thread integer array; this is nearly free for streaming analyses (orderings added at the trace frontier), but an ordering inserted mid-trace must propagate across the whole trace, and vector clocks cannot delete an ordering at all, so a backtracking analysis must rebuild the order from scratch at quadratic cost.
2. CSSTs (Collective Sparse Segment Trees) maintain a small-width partial order with insert, delete, and query all in roughly logarithmic time. The key reduction: dynamic reachability on a few-chain DAG becomes dynamic suffix minima — store each node's earliest reach into each other chain, so a reachability question is a minimum-over-a-suffix lookup — which segment trees solve in log time, with a per-slot min-heap making deletion a cheap heap pop. A sparse tree representation and minima indexing exploit that cross-thread orderings are rare, shrinking the tree (and memory) as sparsity rises, and a collection of one tree per chain pair handles many threads with a cross-chain closure cubic only in the tiny thread count. Where vector clocks are best for streaming analyses, CSSTs are best for non-streaming ones.
3. Across seven analyses from the literature (on an Ubuntu machine, 64 GB), CSSTs outperform vector clocks and the prior segment-tree structure in nearly all cases in both time and memory, handle benchmarks where vector clocks time out and others run out of memory, and run orders of magnitude faster than plain graphs on the fully dynamic linearizability analysis that needs deletion. Its limits: for streaming analyses whose updates barely propagate (C11 race detection), constant-time vector-clock updates still win; a single query is slightly slower than a vector-clock lookup and is cubic in the thread count; the memory and speed edge depend on cross-thread sparsity (worst-case memory is still trace-length times thread-count); and it is a drop-in scalability tool that changes performance, not what an analysis computes.

Check yourself

Check your understanding

1. Why are vector clocks fast for some concurrency analyses but slow for others?
2. What makes deletion of an ordering so important, and why can vector clocks not do it?
3. What is the core algorithmic idea that lets CSSTs run in roughly logarithmic time?
4. Which statement best reflects the evaluation and scope of CSSTs?

Sources

The paper is “CSSTs: A Dynamic Data Structure for Partial Orders in Concurrent Execution Analysis” by Hunkar Can Tunc, Ameya Prashant Deshmukh, Berk Cirisci, Constantin Enea, and Andreas Pavlogiannis, published at ASPLOS 2024 (Best Paper Award), DOI 10.1145/3620666.3651358. The authors are at Aarhus University, IIT Bombay, Amazon Web Services, and Universite de Paris (IRIF); the CSST data structure and the experimental artifact are open-source.

This explainer is written from the full 16-page author-hosted text. Everything above comes from the paper’s own sections: the abstract and introduction framing dynamic concurrency analyses around maintaining a happens-before partial order and the insert/query/delete operations, the cost of graphs (quadratic transitive closure) and vector clocks (linear-in-trace propagation for non-streaming updates, no deletion); the motivating consistency-checking example with reads-from guessing, saturation, cycle detection, and backtracking; the contributions and complexity bounds (fully dynamic updates and reachability queries, the incremental variant, and the novel cross-chain density notion); the preliminaries on chain DAGs, width, and dynamic reachability operations; the Collective Sparse Segment Tree construction reducing reachability to dynamic suffix minima solved by segment trees (the two-chain case with per-slot min-heaps, the sparse segment tree with minima indexing and sparse representation, and the collection with cross-chain transitive closure for many chains); and the experimental evaluation incorporating CSSTs into seven analyses from the literature (M2 race prediction, SeqCheck deadlock, ConVulPOE memory bugs, x86-TSO consistency, UFO use-after-free, C11Tester, and linearizability root-causing) against graphs, vector clocks, and segment trees, reporting the geometric-mean time and memory improvements, the cases where baselines time out or run out of memory, the roughly 3.5-times partial-order-maintenance speedup in use-after-free, the C11 exception where vector clocks win, and the controlled scalability experiments.