Paper by Erik D. Demaine

Reference:

Erik D. Demaine, John Iacono, and Stefan Langerman, “Retroactive Data Structures”, in Proceedings of the 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2004), New Orleans, Louisiana, January 11–13, 2004, pages 274–283.

Abstract:

We introduce a new data structuring paradigm in which operations can be performed on a data structure not only in the present but also in the past. In this new paradigm, called retroactive data structures, the historical sequence of operations performed on the data structure is not fixed. The data structure allows arbitrary insertion and deletion of operations at arbitrary times, subject only to consistency requirements. We initiate the study of retroactive data structures by formally defining the model and its variants. We prove that, unlike persistence, efficient retroactivity is not always achievable, so we go on to present several specific retroactive data structures.

Length:

The paper is 10 pages.

Availability:

The paper is available in PostScript (208k), gzipped PostScript (63k), and PDF (138k).

See information on file formats.

[Google Scholar search]

Related papers:

Retroactive_TALG (Retroactive Data Structures)

FullyRetroactive_WADS2015 (Polylogarithmic Fully Retroactive Priority Queues via Hierarchical Checkpointing)

RetroactiveSeparation_SWAT2018 (Nearly Optimal Separation Between Partially And Fully Retroactive Data Structures)

RetroactiveSeparation_ISAAC2022 (Lower Bounds on Retroactive Data Structures)