The bug is three weeks old before anyone notices. A job has been writing the wrong value into a column the whole time, and every average, every chart, every alert threshold built on that column has been wrong for twenty-one days.
The standard fix is to replay. Find the offending operation, wind the state back to just before it, correct it, and run everything forward again. It works, and it costs as much as those three weeks cost the first time. Run it again for the next bad operation in the same window and you pay again.
There is a name for the thing that would fix this properly, and almost nobody uses it. A data structure is retroactive if you can insert or delete an operation at an arbitrary point in its history and have the present behave as though that had always been the history. Not a replay, and not a snapshot either. A real edit to the past, with the consequences already accounted for.
The part that is easy to miss is that an operation in the past is still live. Every later answer reads it.
Two ways to travel through time
Computer science has been thinking about time inside data structures for decades, but almost always in one direction. Persistent data structures keep every version. You change something, you get a new version next to the old one, and the old ones never move. Driscoll, Sarnak, Sleator and Tarjan showed in 1989 that any pointer-based structure can be made persistent with constant amortized overhead, which is why this is the version that shipped everywhere. Git is a persistent tree. So is every copy-on-write filesystem, and so is the MVCC machinery inside Postgres.
Retroactivity runs the other way, and it is much stranger. There is one timeline. Operations sit on it, and you can insert a new operation at any point in the past or delete one that is already there. The present is then whatever the timeline now says it should be. Nothing is archived, because nothing is allowed to be a frozen copy. One edit near the beginning can change the state at every later moment, which is exactly what persistence promises will never happen.
Demaine, Iacono and Langerman formalised this in 2004 and gave it the best phrase anyone has found for it: the plastic timeline.
Figure 1. Persistence forks the timeline and leaves the archive alone. Retroactivity keeps one timeline and rewrites its tail.
The distinction that matters in practice is partial versus full. A partially retroactive structure lets you edit the past but only lets you look at the present. A fully retroactive one lets you query any moment as well. Partial is what most systems actually want, because the question an incident review asks is “what is true now, given this correction”, and it asks nothing about the intervening states.
Why time is not another dimension
The obvious objection is that time is a coordinate, so why not add it as one. Represent a min-heap as a plane: time along the x axis, key values up the y axis. Every element becomes a horizontal segment running from the moment it was inserted to the moment it was deleted. Every delete-min becomes a vertical ray shooting up from below until it hits the smallest segment available. Insertions pair with their deletions into little L shapes that never cross. It is a genuinely clean picture, and I have stared at it for a while.
Then you insert one operation at the start, and the picture falls apart. Every segment’s right endpoint moves.
Figure 2. Six key lifetimes on one axis. Grey is what each key’s life looked like before the edit, green is the time the edit adds to it. One small key inserted near the start lengthens every lifetime in the chain and pushes the largest key back into the present.
Not some of them. In the worst case all of them, and the L shapes get rebuilt. The paper’s first figure is this exact picture, and it is the reason retroactive data structures are not a two-dimensional geometry problem with an extra axis bolted on. The x axis is the direction the dependencies run in, and a local change to it is not local.
What it costs
Here is the uncomfortable part, and it is a theorem rather than a gap in current software.
There is a general method, and it is the one your system already uses. Log enough information to reverse every operation. To make a retroactive edit, undo everything after the edit point, apply the change, then redo what you undid. The paper calls it rollback. If the base structure costs T(n) per operation and the edit reaches r operations back into the past, a retroactive update costs O(r T(n)). Retroactive work is priced by distance.
You might hope a cleverer representation beats that. It cannot, in general. The same paper exhibits a data structure with O(1) operations where any partially retroactive version needs Ω(r). The witness is worth reading because it is tiny. Keep two numbers, X and Y, both starting at zero, and allow three operations: add a constant to X, add a constant to Y, and multiply Y by X. Run a sequence that adds to Y, multiplies, adds to Y, multiplies, and so on, and at the end both X and Y are zero. Now retroactively insert “add x to X” at the very beginning. The present value of Y becomes a polynomial of degree n evaluated at x, and evaluating a degree-n polynomial takes Ω(n) arithmetic steps no matter how you prepare for it. One operation inserted at time zero, and the price of knowing the answer now is the length of the history.
Frandsen, Hansen and Miltersen get a weaker bound even in the cell-probe model, where a structure is charged only for memory accesses: Ω(√(r / log r)). In 2022 Chung, Demaine, Hendrickson and Lynch closed most of the remaining gap, proving that under any one of three standard fine-grained conjectures the rollback method’s linear overhead is essentially optimal.
The authors put it in terms I like more than the formal statement. Applied to time travel in general, it says that making a change in the past and then jumping forward to the present should cost roughly as much computation as the universe needed to advance through that much time the first time. Which is a decent argument that the time travel in the movies is not implementable.
The two conditions that make it cheap
All of that is the general case. The general case is not the case you are usually in.
The first condition is commutativity plus invertibility. If the state of your structure does not depend on the order in which operations were applied, then applying an operation in the past is the same as applying it now, and the retroactive version costs nothing extra. Add an inverse for every operation and deletion becomes free too. A running sum is the trivial example, and it is not a toy: searchable dynamic partial sums, where you add a value to an array cell and ask for prefix sums, is commutative and invertible and therefore automatically retroactive. So is any pure searching problem, which is a set with insertions, deletions, and queries against a new object, because a set is unordered by definition. Dictionaries. Dynamic convex hulls. Planar width.
The second condition is decomposability. A searching problem is decomposable if a query against a union of two sets can be assembled in constant time from the answers against each set separately. Bentley and Saxe showed in 1980 that this is enough to turn a static structure into a dynamic one, and Demaine and coauthors showed it is also enough to make the structure fully retroactive. The construction is the one you would guess once you see the picture. Draw every element as a segment from its insertion to its deletion. Build a segment tree over the timeline. Keep one structure per node, holding the segments that node represents. Each element occupies O(log m) nodes, each retroactive update touches O(log m) structures, and a query at any point in time unions O(log m) answers back together. Fully retroactive, with the past queryable.
What is left after those two conditions is the interesting residue: structures whose operations genuinely depend on the order they were applied in. A priority queue is the clean example, because delete-min is the operation that cannot commute with anything. Which element gets deleted depends on everything that came before it.
The heap you can edit
The retroactive priority queue is the result I keep coming back to, because the construction is a real idea rather than a trick, and because it is where the geometry earns its keep.
Start with the segment picture. Keys up the y axis, time along the x axis, each key a horizontal segment from insertion to deletion. Add the rule that delete-min always takes the smallest key available, and the picture becomes a staircase: the segments never cross, and the vertical rays from delete-mins hit them in order.
Now do the retroactive insertion. Add a key at a point in the past. Exactly one element has to appear in the present, because the count of live elements has to go up by one. Which one? The largest key among those deleted after the insertion point, or the new key itself if it is bigger. Everything between the insertion point and the present shifts by one step, which in the picture is a chain of lifetimes each lengthened by exactly one interval.
Deciding which key that is, without walking the chain, is where the work goes. The trick is to stop thinking about the heap and start thinking about a running total over the operation list. Give each operation a weight. An insertion whose key is gone by the present time is +1. An insertion whose key is still there is 0. A delete-min is -1. Then define a bridge as a moment in the history where the running total is zero.
That definition looks arbitrary for about ten seconds. It is not. The running total at a moment counts the live keys that are still going to be deleted later. Zero therefore means every key currently in the heap survives to the present, which is exactly the condition the construction needs. A bridge is a moment where the edited past and the present line up.
Figure 3. The same operation list with weights: +1 for an insertion whose key is gone by the present, 0 for one whose key survives, -1 for a delete-min. The step line is the running total, and the dotted lines mark the bridges, where it returns to zero.
With that in hand the rest is bookkeeping. Maintain the operation list with prefix sums, so you can find the last bridge before a time or the first bridge after it in O(log m). Maintain the insertions in a balanced tree augmented with, at each node, the largest key in the subtree that is not in the present heap and the smallest key that is. A retroactive update then becomes: find the neighbouring bridge, read off one extreme, add or remove one key, update one weight. That is O(log m) per retroactive update, and queries about the present stay O(1), because the present heap is maintained explicitly.
That is the partially retroactive priority queue. Full retroactivity for a priority queue took eleven more years and a different idea, hierarchical checkpointing, and landed at polylogarithmic time as well. The queue and union-find come out in logarithmic time or better, and none of the machinery is exotic once the model is set up. It is ordinary data structures work with an unusual objective.
| structure | partially retroactive | fully retroactive |
|---|---|---|
| queue | O(1) | O(log m) |
| union-find | O(log m) | O(log m) |
| dictionary, exact search | O(log m) | O(log m) |
| priority queue | O(log m) | polylog since 2015 |
Worst-case time per operation, from Table I of the 2007 paper, where m is the number of operations. The fully retroactive priority queue entry is the one the 2015 paper supersedes.
Where this already shows up
Here is the part I find genuinely interesting, and it is the reason I wanted to write this rather than just link the paper.
The two conditions are not academic. They are the design constraints that the systems which actually cope with reordered history have independently converged on, usually without naming the theorem.
Differential dataflow, the incremental computation model behind Materialize, represents a collection as a sum of differences rather than as a sequence of states, and those differences form an abelian group. Adding a record and removing it are inverse operations, and the order of the additions does not matter. That is the commutative and invertible condition, arrived at from the systems side by asking what makes incremental maintenance cheap. It is why differential dataflow can absorb an insertion somewhere in the past of a dataflow graph and hand back the corrected answer, which is retroactivity at scale.
Conflict-free replicated data types take the other half. Replica merge in a CRDT is commutative, associative and idempotent, which is the condition that makes convergence order-independent, and it is the same lever. The interesting asymmetry is what they gave up. CRDTs are commutative but not invertible, and that is why deletion in a CRDT is famously awkward, with tombstones and unique tags doing the work that an inverse operation would do in a group. The theory predicts the awkwardness. Commutativity buys you reordering. Invertibility buys you deletion. Most systems get one.
System-versioned tables in SQL:2011 are the third case, and the one closest to the segment picture. A row carries a validity interval, an update for part of a period splits that interval, and a query as of a moment asks which intervals cover it. That is the segment tree wearing a database hat, and it works because row-interval insertions and deletions are decomposable.
I want to be careful about what I am claiming. I do not know of a case where one of these systems read the retroactive data structures paper and implemented it. What I am pointing at is that the same condition keeps turning up as the thing that makes order-independence cheap, which suggests the condition is the real object and the applications are instances of it.
What it does not do
Three things retroactivity does not do, and they are the honest limits.
It does not tell you what to change. The structure is handed a list of edits. It cannot know that a sensor was faulty or that a payment went to the wrong account. That judgement stays outside the data structure, which is why every example in the paper is framed as who decided the operation was wrong.
It does not relax consistency. A delete still has to follow an insert. Nothing stops you from constructing an invalid history, and the structures assume you will not, which means a real implementation has to check.
And it is not free at scale. The logarithmic priority queue is a worst-case bound on one abstract data type. The general bound is the one from the lower bounds section, and most production systems sit much closer to rollback than to the retroactive optimum. If you take one practical thing away, take the pricing: a retroactive edit costs roughly what the distance into the past costs, unless your operations commute.
There is also a third flavour I have not mentioned, and it is the one an incremental system actually wants. Retroactivity as I have described it is oblivious: the edit changes the internal state, and nothing outside the structure is told which answers moved. Tangwongsan called the alternative active data structures, where an operation in the past also reports which later results take on new values. It is a harder problem, because the structure has to track what every outside party has already read, but being told which answer changed is far more useful than recomputing all of them and hoping somebody notices the difference.
What I take from it
A week ago I wrote that physics has no delete key, only a stirrer. Data structures do have one. What they do not have is a cheap one, and the price is set by distance.
Which leaves me with the thing I actually took from reading this literature. We spend enormous effort on storage and almost none on the shape of our update operations, and the shape is what decides whether correcting the past is cheap or impossible. A log of order-free, invertible updates can be corrected anywhere, at any time, for nothing. A log of order-dependent decisions can only be corrected by living through them again. That is a design decision, and it is usually made by accident, long before anyone has a reason to think about it.
If you build systems, the practical version is short. Make your updates commutative and invertible where you can, because that is the case where editing the past costs nothing at all. Where you cannot, keep the edit close to the present, because distance is the price. And if you are building anything that will one day need to answer what was true then, decide now whether you are keeping an archive or maintaining a timeline, because those are different data structures and the choice is the hard one to reverse.