This paper presents a general technique to transform any pointer-based data structure into one that is “confluently persistent,” thus answering a longstanding open problem posed by Driscoll, Sarnak, Sleator, and Tarjan [1], and refined by Driscoll, Sleator, and Tarjan [2]. An initial configuration of a data structure is version zero, and every subsequent update operation creates a new version of the data structure. A “fully persistent data structure” has the property that every version can be both accessed and modified. “Confluently persistent” refers to fully persistent data structures that support meld operations that combine two different versions of a structure, as in set union or list catenation. The main contribution of this paper is to show that confluently persistent data structures are feasible.

The paper is organized into sections. The introductory section is quite good at setting the framework for how this paper differs in approach from the foundational works cited above. The heart of the approach taken is a “version DAG” (DAG stands for acyclic directed graph) that allows an update to any version of the underlying data structure that coexists with all previous versions. The second section presents a lower bound on the space requirement for any general scheme that will make a data structure confluently persistent. The third section contains a brief overview of the previous “fat node method” for fully persistent data structures. The fourth section addresses the “full path method,” which is a straightforward means of making a data structure confluently persistent. The fifth section describes the “compressed path method,” which provides certain advantages for some data structures. The sixth section is concerned with randomized variations of the full path and compressed path methods that can provide significant time speedup results. As one would expect, the constant theme throughout this paper is one of tradeoffs between space and time. The final section provides brief concluding remarks that include a suggestion for future work.

The general presentation of the paper is effective, carefully written, rigorous, and complete, with helpful tables and figures that illustrate and support the text. This paper represents a significant contribution to the design and analysis of algorithms.