15 Research from 2005

These chapters preserve cxOT research documents written in 2005. They are presented in chronological order and may describe superseded terminology, algorithms or conclusions.

Historical overview (editorial note)

The research developed along two connected strands: establishing mathematically correct operational transformation algorithms, and finding spatial representations of changes that could be merged without the quadratic cost of transforming one temporal list of atomic operations against another. David Barrett-Lennard recalls that these ideas were already being explored during 2004 and early 2005, before they appeared in the dated papers collected in this chapter.

The performance strand is already explicit in the Log Compression Algorithm of 15 July 2005. It represents a change as ordered lists of deletion and insertion intervals and merges two changes with a left-to-right scan, linear in the number of intervals. This records the idea that practical reconciliation required changes to be represented spatially and merged as composite state differences, rather than retained only as chronological sequences in linear history buffers.

The Single Character Insertion and Deletion Operations paper of 26 July had a different immediate purpose: to get the mathematics right on the simplest atomic operation set before returning to multi-character and composite changes. Work on the TP2 puzzles had shown that insertion-only and deletion-only cases were not problematic; the puzzles arose from their interaction. After reading Du Li and Rui Li's work on the operation effects relation in early 2005, Barrett-Lennard realised that insertion positions should be tracked as though deletions had not taken place. This became the Effects Document and preserved the ordering information needed for insertions. Li and Li's effects relation was the key inspiration for that correctness result.

The Multi-character Insertion and Deletion Operations paper of 29 August then lifted the single-character mathematics to changes made of multiple intervals. In September, Merging Operations introduced the operator ⊕ for replacing contextually serialised operations by a single composite operation. These papers should therefore be read as stages of one programme: retain the correctness insight supplied by the effects relation while developing spatial, mergeable representations that avoid quadratic list-against-list reconciliation.

The later INRIA work on Tombstone Transformation Functions independently used the related idea of retaining deleted characters as stable ordering landmarks and formally checked its transformation functions against TP1 and TP2. It addressed the correctness of atomic transformations, but did not by itself remove the quadratic reconciliation costs of temporal history-buffer representations. That performance problem is the reason the interval, composite-operation and merge work from this period is historically distinct as well as complementary.