66 String insertion DualIT is harder on composite operations

Review of algorithm on atomic operations

We say an operation is atomic if it represents a particular op(s,t) for some siteid s and sequence number t.

If O₁ and O₂ are atomic concurrent context equivalent insertion operations on a text field then merging the operations involves dual IT, and this in turn simply involves comparing q-positions of the insertion intervals, or in the case of coincident insertions (i.e. at the same q-position), the order is determined by a comparison of siteids - where we follow the convention that an insertion with a lesser siteid appears before an insertion with a greater siteid in the resulting merged text. See Single character insertion and deletion operations. This algorithm was developed around January 2005.

It is straightforward to generalise single character atomic operations to multi-character atomic operations. That means an atomic operation can represent arbitarily complicated changes to a text field - it can insert and delete multiple characters at multiple positions. See Multi-character insertion and deletion operations. This algorithm was developed around August 2005.

Even though we have supported atomic operations that can insert and delete multiple characters at multiple positions, the algorithms from 2005 require the atomic operations to be recorded in temporal order in "history buffers", and the algorithms to factorise a history buffer into prefix and suffix for a given vector time tend to be quadratic in the number of atomic operations, as is the dual IT of two lists of operations.

What about composite operations?

In 2008 work was undertaken to have a concept of merging atomic operations into composite operations, and to use the concept of extracting and applying RFactors to synchronise sites. This eliminates the whole need for history buffers - i.e. linear lists of atomic operations in a temporal order that respects causal order. This would allow for extracting and merging Rfactors in linear rather than quadratic time.

We might guess that the same approach of comparing q-positions then siteids will work on left-to-right scans through the insertion intervals recorded in composite operations. Unfortunately, it doesn't work.

Another idea could be to have a concept of effective siteids which are inherited from coincident insertions which causally precede it. Unfortunately, siteid inheritance doesn't work.

Yet another idea is to record effective siteids in the intervals, and use these for the dual IT, and to recalculate the effective siteids when applying local insertions. Unfortunately, calculating effective siteids when applying local operations doesn't work.

Yet another idea is to simply make the rule that when we dual IT coincident insertions we scan right to left through the intervals with a larger sitid to find the insertion position. Unfortunately, it doesn't work.

A correct solution is to calculate transient effective siteids on sets of maximal q-contiguous intervals each time we dual IT RFactors from two sites.

Dual IT of O₁,O₂ again

Let O₁ <> O₂. Consider that Ψ(O₁) contains O_x,O_y with O_x → O_y. Let each insertion interval in an operation record the vector time of the context in which it was originally generated. Let gc(O_y) denote the generational vector time of atomic operation O_y.

Then as discussed in Vector Time

O_x → O_y iff O_x ∈ 𝜒(gc(O_y)).

Given non-empty operation O,

∃ O_y ∈ Ψ(O) such that (¬ ∃ O_x ∈ Ψ(O) such that O_x → O_y).

Hence O can be factorised into O = O_x ⊕_>> O’ for some O’. It follows that given O₁, O₂ we can factorise out atomic LFactors like this:

O₁ = O_x ⊕_>> O₁’
O₂ = O_y ⊕_>> O₂’

This provides a conceptual basis for recursively decomposing the problem into a simpler one (using properties MP3 and MP4 from Operational transform Merging operations).

The largest LFactor we can take

For given operation O, it would seem appropriate to take the largest LFactor such that there are no causal dependencies between any two atomic operations within the LFactor.

Lf = { O_y ∈ Ψ(O) | ¬ ∃ O_x ∈ Ψ(O) such that O_x → O_y }

It is obvious that such a factorization doesn’t violate causality (ie there is no O_x ∈ Ψ(Rf) and O_y ∈ Ψ(Lf) such that O_x → O_y).

Note that all operations within Lf are concurrent. Therefore we should find that intervals in Lf are ordered by siteid, and therefore there is a unique insertion position.