<p>Suppose I have an algorithm which maintains a data structure $A$. After the algorithm has run up to time $t_2$, it decides to back-track to a prior state $t_1$. It should be possible to restore the state of $A$ to what it was at time $t_1$ by simulating $A$, instead of running it directly, and maintaining a log of all changes made to $A$. The total time needed to unwind the state of $A$ to time $t_1$ should be $O(t_2 - t_1)$, possibly with some logarithmic factors</p>

<p>I have a few questions about this ---</p>

<p>(1) Does this principle have a name?</p>

<p>(2) Do I have to pay logarithmic factors for simulating $A$ instead of running it? I would like to avoid this if possible. Is there a model of computation, such as the RAM model, that avoids this? Or are there some regularity conditions?</p>

<p>Thanks!</p>

<p>EDIT: Some search of the literature shows that this is called the "rollback method". It seems to be a folk theorem that the RAM model supports linear-time rollback. I am a little surprised that there is nothing proved formally and no papers cited, as (for example) the Turing Machine model requires a logarithmic slowdown.</p>

CC BY-SA 3.0
2011-07-14T17:17:10.053Z
Maybe you want to look at [persistent data structures](http://en.wikipedia.org/wiki/Persistent_data_structure).
Dave Clarke
CC BY-SA 3.0
2011-07-14T17:25:52.580Z
This helps but doesn't address the question directly. Persistence seems to involve more general operations than simply unwinding. The theorems that are proved are not very generic. I only need to perform a single type of back-tracking, and I want to very open-ended about the data structure involved.
David Harris
CC BY-SA 3.0
2011-07-14T21:10:11.880Z
You need to be a little careful here: rollback doesn't mix well with amortization.
David Eppstein
<ds.algorithms>
Unwinding a data structure to a previous state
David Harris
# Unwinding a data structure to a previous state

(Asked by: username_0 on 2011-07-14)

Suppose I have an algorithm which maintains a data structure $A$. After the algorithm has run up to time $t\_2$, it decides to back-track to a prior state $t\_1$. It should be possible to restore the state of $A$ to what it was at time $t\_1$ by simulating $A$, instead of running it directly, and maintaining a log of all changes made to $A$. The total time needed to unwind the state of $A$ to time $t\_1$ should be $O(t\_2 - t\_1)$, possibly with some logarithmic factors

I have a few questions about this ---

(1) Does this principle have a name?

(2) Do I have to pay logarithmic factors for simulating $A$ instead of running it? I would like to avoid this if possible. Is there a model of computation, such as the RAM model, that avoids this? Or are there some regularity conditions?

Thanks!

EDIT: Some search of the literature shows that this is called the "rollback method". It seems to be a folk theorem that the RAM model supports linear-time rollback. I am a little surprised that there is nothing proved formally and no papers cited, as (for example) the Turing Machine model requires a logarithmic slowdown.

**Tags:** ds.algorithms

> **Comments:**
> **username_1**: Maybe you want to look at [persistent data structures](http://en.wikipedia.org/wiki/Persistent_data_structure).  
> **username_0**: This helps but doesn't address the question directly. Persistence seems to involve more general operations than simply unwinding. The theorems that are proved are not very generic. I only need to perform a single type of back-tracking, and I want to very open-ended about the data structure involved.  
> **username_2**: You need to be a little careful here: rollback doesn't mix well with amortization.  

---

## 0 answers

