This is a note on an idea that I have heard called the reverse delta scheme. It is not very profound—yet I recall my surprise when I first heard of it. Google leads to little insight on the term. There are references to “reverse deltas” in the context of RCS, but no descriptions.

First I introduce two nice terms from Xanadu for two common ideas:

Work
A body of information that undergoes or has undergone gradual modifications over time.
Edition
A particular state of a work—a snapshot of the work at some particular instant, or perhaps one of several concurrent candidate states, competing to become the true next state. An edition is immutable.

It is often desirable to keep past editions of a work that do not much differ from each other. It may be possible and convenient to store differences (“deltas” here) between these editions, rather than the editions themselves. Less storage is required and reconstructing the alternate editions may be faster than retrieving them from the alternative larger slower storage required if the redundancy is not exploited.

The Reverse Delta

The simple idea of the reverse delta is that the most heavily used version, probably the most recent, is the one that should be kept as the base edition. The deltas allow reconstruction of successively older editions from more recent editions.

Forward deltas have been used to save time and space in storing past and current versions of the source of software. The first such that I used was part of IBM’s CMS development environment circa 1970. It used only forward deltas. The deltas were produced directly by the interactive editor.

Ramifications

Some storage media may be written only once or perhaps just a few times. Such media would limit the application of this idea. Various combinations of these two schemes provide the combined advantages—providing tradeoffs between Using either forward or reverse deltas may reveal an implicit vulnerability to media failure. With delta technology, a media failure may decimate many editions. I think the solution is to employ any of several available technologies that provide reliable storage systems, built if necessary upon less reliable storage.

Orthogonal Trick: Composable Deltas

Some formats for expressing deltas lead to algorithms which allow for the efficient composing of two deltas into a third without reference to the base file. This may avoid multiple passes over a file when multiple deltas are required for the desired edition. RCS and IBM’s CMS system both exploit this trick.

Early Publication

The first publication of this idea that I am aware of is at:

Lars-Henrik Eriksson, Ken Kahn, and Manny Rayner.
Incorporating mutable arrays into logic programming.
Technical report, University of Uppsala, UPMAIL, July 1984.
Also in Proceedings of the Second International Logic Programming Conference.

Extant Delta Technologies

The Unix “diff” command, operating on files X and Y, is able to produce directions to an editor to modify X to obtain Y.

The IBM CMS editor was able to produce deltas for new editions, or to modify deltas instead of modifying editions.

The RCS system employs reverse deltas. See A System for Version Control by Walter F. Tichy,

The definition of “reverse delta storage” given in the Perforce Manual suggests what I would call forward deltas, with the latest edition also available directly.