A tree clock data structure for causal orderings in concurrent executions

Almost every tool that hunts for data races by watching a program run keeps a vector clock per thread — a flat array of one counter per thread — and merges two of them every time threads synchronise, which costs one pass over the whole array no matter how little actually changed; this paper replaces the array with a tree whose shape records how each piece of knowledge arrived, so a merge can stop descending the moment it reaches a thread the receiver already knows about, making merges cost roughly what genuinely changed rather than the thread count, and proving that for the classic happens-before relation no data structure can do asymptotically better on any input.

Why this problem is worth solving

The value of dynamic analysis is that it inspects one real execution rather than reasoning about all of them, and the cost is that it has to keep up with the program.

What the paper attacks is the gap between the work performed and the work necessary.

What people did before, and where it broke

• Use vector clocks and accept the linear cost. This is the state of practice and has been for decades. It is simple, correct, and its comparison operation falls out for free. Where it broke. Every merge and every copy is a full pass over the array, so the cost grows with the thread count regardless of how much information actually moved. The paper’s framing is that any improvement must be sublinear — it must not even look at some entries — which is a high bar for an operation that is already just a loop over an array.
• Compress the representation by exploiting structure in traces. A line of work finds special structures that permit succinct encodings of vector times. Where it broke. These depend on the trace having the structure, and there are known theoretical limits on how far succinct representations can go in general.
• Avoid vector timestamps entirely. One well-known algorithm infers the ordering using locksets instead of timestamps. Where it broke. The paper reports it incurs severe slowdown, citing the measurement from prior work.
• Optimise the common case with epochs. The widely used approach replaces a full vector with a single thread-and-time pair wherever one suffices, which is very effective for the per-variable access histories that dominate a race detector. Where it broke. It optimises a different set of clocks. Epochs shrink the metadata attached to memory locations; the clocks carried by threads and locks still have to be merged in full. The paper explicitly positions itself as complementary rather than competing here, and in fact uses epochs in both arms of its own comparison.
• Attack the other bottlenecks instead. Instrumentation cost and metadata synchronisation are also large, and have been addressed with hardware assistance, hybrid detection, static pre-analysis and ownership protocols. Where it broke. These are real and useful, and orthogonal — none of them makes the merge itself cheaper.
• The gap. Nobody had asked whether the array is the right shape. The redundancy in a merge is not accidental or data-dependent noise; it follows from transitivity and is in principle predictable. But predicting it requires knowing how each piece of knowledge was acquired, and that is exactly the information a flat array discards.

How a tree clock avoids looking at most of itself

The idea

A flat array cannot express transitivity, so it repeats work it could prove unnecessary. The motivating example in the paper is worth following. Six threads; one merges another array; four of the six entries end up unchanged. That is not bad luck. The sender learned about those four threads through a single intermediary, and the receiver already has fresher news about that intermediary — so by transitivity, everything reaching the sender by that route is guaranteed stale for the receiver. The reasoning is airtight and completely unavailable to a vector clock, which knows what each thread thinks but not how it came to think it. Storing the same counters in a tree makes the route explicit, and the pruning rule falls straight out of it. Reorganising a data structure so that a traversal can stop early rather than making each step of the traversal faster is the same class of move as the page-walk restructuring work covered elsewhere on this site, where the win came from changing the shape of the thing being walked.

Two pruning rules, and the difficulty is preserving them. The first, direct monotonicity, is the one above: do not descend into a node whose thread the receiver is already ahead on. The second is subtler. Each node also stores the moment at which its parent learned of it, and siblings are ordered by that moment. So if the receiver already knows about a sibling attachment as recent as this one, everything later in the sibling list was attached even earlier and is therefore also already known — the scan can stop. Both rules are easy to state and neither is the hard part. The hard part is that after a merge you must rebuild the modified region of the tree so that both properties still hold for every operation that follows, which is most of the algorithmic work in the paper. Buying a strong guarantee by getting the structure right, rather than by searching harder at runtime, is the opposite bargain from the differentiable extraction work covered elsewhere on this site, which gave up guarantees entirely in exchange for a search that moves fast.

The optimality claim is about the work an input demands, not the worst case. This distinction is easy to miss and is what makes the result interesting. The paper defines the vector-time work of a trace as the total number of counter entries that genuinely change over the whole run — a quantity that depends on the trace and not on any data structure — and shows that computing happens-before with tree clocks takes time within a constant factor of it, on every input, with the constant being three. Vector clocks are demonstrably not optimal in this sense; there are traces where they do a factor of k more work than necessary. But the worst case is unchanged: with an adversarial trace where the necessary work really is quadratic, tree clocks are quadratic too. The guarantee is that you never do much more than the input actually requires, which is a stronger everyday promise than a worst-case bound and a weaker headline. That a technique behaviour depends entirely on the shape of its input, and that you only learn this by measuring across many inputs rather than a handful, is the same lesson as the runtime prefetching work covered elsewhere on this site.

Walking one merge through a tree clock

This is already the structural difference. A vector clock merge has no notion of where to begin because every entry is equally reachable; a tree has an entry point, and the entry point is the piece of information most likely to matter.

Why it works

• The redundancy follows from transitivity, so it can be predicted rather than discovered. If a thread is already ahead on some intermediary, everything learned through that intermediary is already stale → the whole subtree can be skipped without reading it → the merge becomes sublinear rather than merely faster per entry.
• The tree shape is free information the array was throwing away. The counters are identical; only the arrangement differs → the arrangement encodes how each fact arrived, which is exactly the premise the pruning argument needs → no extra bookkeeping is required beyond a parent pointer and an attachment time.
• Ordering the children turns a scan into an early exit. Siblings are kept in decreasing order of when the parent learned of them → meeting one the receiver already covers proves every later sibling is older still → the second pruning rule costs a comparison rather than a traversal.
• The guarantee is measured against the input rather than the worst case. Optimality is defined relative to how many counter entries genuinely change in this particular trace → tree clocks stay within a factor of three of that on every input, while vector clocks can exceed it by a factor of the thread count → the promise holds for all inputs rather than for a favourable class of them.
• Nothing above the data structure has to change. Comparison, increment and copy keep their meanings, and the epoch optimisation still applies → an existing detector or model checker can swap the structure and keep its algorithm → which is why the same change works for three different partial orders in the evaluation.

What it costs (trade-offs and scope)

• The end-to-end speedup is far smaller than the headline, and for one partial order it nearly vanishes. Computing the ordering alone gets 2.02, 2.66 and 2.97 times for the three relations. Once the surrounding analysis is included, those become 1.49, 1.80 and — for happens-before, the one with the largest raw speedup — just 1.11 times. The abstract quotes only the first set of numbers.
• The reason for that gap is structural, not incidental. Happens-before is defined only over synchronisation events, and the paper measures those as about 9.5% of events in its traces. So the part being sped up is a small slice of the total work. The authors say this plainly and note the speedup rises with the proportion of synchronisation events, which their own scatter plot confirms.
• The theoretical ceiling is far above what is achieved. The paper measures that vector clocks perform up to 55 times more entry updates than tree clocks on some traces, yet the realised speedup is around 3. The stated reason is that a single tree clock operation is more expensive than a single array step — pointer chasing against a linear scan.
• The worst case is unimproved. Computing happens-before with tree clocks is still quadratic in the worst case, exactly as with vector clocks. The optimality result is relative to the work a given trace demands, not an asymptotic improvement.
• There are traces where it is slower. The paper reports these as few and the margin as small, attributing them to cases where the sublinear updates offer little to gain and the overhead of the more complex structure is not repaid.
• A specific communication pattern defeats it entirely. In a controlled experiment where every pair of threads communicates through its own dedicated lock, the benefit is nullified and the added complexity produces a general slowdown. The authors identify this as the worst case and note the gap remains small — but it is a real pattern, and the star topology at the other extreme is where the structure shines, with time staying flat as threads are added.
• Memory roughly doubles. The implementation is two arrays of length k, one for the counters and one for the tree shape, where a vector clock needs one.
• The extension to other orderings is partly promissory. Three partial orders are implemented and measured. Several others are named as promising, with the caveat that they may require small extensions to the data structure, and those are not carried out here.

The evaluation

Check yourself

Sources

The paper is “A Tree Clock Data Structure for Causal Orderings in Concurrent Executions” by Umang Mathur, Andreas Pavlogiannis, Hunkar Can Tunc and Mahesh Viswanathan, published at ASPLOS 2022, pages 710-725, DOI 10.1145/3503222.3507734. The authors are at the National University of Singapore, Aarhus University, and the University of Illinois at Urbana-Champaign.

This explainer is written from the full text, read from the authors’ preprint on arXiv (2201.06325). Everything above comes from the paper’s own sections 1 through 6: the motivating six-thread example where four of six entries are provably unchanged; the definitions of traces, thread order and local time; the vector clock interface with its merge, copy, increment and comparison operations, all linear in the thread count; the two pruning principles of direct and indirect monotonicity with their worked examples; the tree clock definition with its nodes carrying a thread identifier, a clock value and an attachment time, its child lists kept in decreasing attachment order, and its thread map; the merge and monotone copy algorithms with their detach and attach phases and the case where the old root must be demoted; the observation that worst-case complexity remains quadratic; the definition of vector-time work and the theorem placing tree clocks within a factor of three of it on every input, along with the remark that vector clocks are not optimal in this sense; the implementation as two arrays of length k with recursion made iterative; the 153 benchmark traces from the IBM Contest, Java Grande, DaCapo and SIR suites plus several OpenMP collections; the speedup table giving 2.02, 2.66 and 2.97 for the orderings alone against 1.49, 1.80 and 1.11 with the analysis included, and the explanation via the 9.5% figure for synchronisation events; the observation that vector clocks perform up to 55 times more entry updates while realised speedup is around 3; and the four controlled topology experiments, including the star topology where time stays flat and the all-pairs topology identified as the worst case.