Efficient pebbling for list traversal synopses with application to program rollback

We show how to support efficient back traversal in a unidirectional list, using small memory and with essentially no slowdown in forward steps. Using O(lgn)$O(lgn)$ memory for a list of size n$n$, the i$i$’th back-step from the farthest point reached so far takes O(lgi)$O(lgi)$ time in the worst case, while the overhead per forward step is at most ?$?$ for arbitrary small constant ?>0$?>0$. An arbitrary sequence of forward and back steps is allowed. A full trade-off between memory usage and time per back-step is presented: k$k$ vs. kn^1/k$k{n}^{1/k}$ and vice versa. Our algorithms are based on a novel pebbling technique which moves pebbles on a virtual binary, or n^1/k$n^{1/k}$-ary, tree that can only be traversed in a pre-order fashion.