21.3 Composite operations for insertions into a string

Let the document state be a text field (i.e. a single string of characters), and the only operations are stringwise insertions. Let an operation store the following state:

The vector times v_in and v_out.
A vector<Entry> ordered by insertion position, specified in post-insertion coordinates.

struct Entry
{
    SiteId s;
    int t;
    int q;      // insertion position
    string str; // string to be inserted
};

Operation LFactor(O,v)
{
    int offset = 0;
    Lf.vin = O.vin;
    Lf.vout = v;
    Lf.entrys = [];
    for each e in O
    {
        if (e.t < v(e.s)) Lf.entrys += Entry(e.s, e.t, e.q - offset, e.str);
        else offset += e.str.size();
    }
    return Lf;
}

Operation RFactor(O,v)
{
    Rf.vin = v;
    Rf.vout = O.vout;
    Rf.entrys = [];
    for each e in O
    {
        if (e.t >= v(e.s)) Rf.entrys += e;
    }
    return Rf;
}

Operation MergeContextEquivalent(O1,O2)
{
    int offset1 = 0;
    int offset2 = 0;
    // linear scan through both lists, shifting to right according to the other
    // offset. When offset insertions are at the same place then resolve
    // the tie using siteid comparisons. Accumulate offsets as we go.
}

Operation MergeContextSerialised(O1,O2)
{
}

Ensuring MP3

Let O₁,O₂ represent insertions on a single text field. Each operation records insertion intervals ordered by q-position.

Let O₁ <> O₂. The dual IT of O₁,O₂ involves simultaneous left-to-right scans through both O₁ and O₂ in a manner reminiscent of merge sort. As the algorithm proceeds we accumulate a counter of the total number of characters inserted so far by O₁. Similarly we have a counter for O₂. In order to compare the positions of the next interval from O₁ and the next from O₂, we must offset the interval from O₁ to the right by the number of insertions by O₂. Similarly we must offset the interval from O₂ by the number of insertions by O₁.

If the positions compare equal then it would appear we must compare siteids to break the tie. This suggests the following algorithm:

struct Interval
{
    SiteId s;
    int t;
    int q;
    string str;
    Interval* next;       // ptr to next interval, or NULL
};

void DualIT(Interval* i1, Interval* i2)
{
    int s1 = 0;     // Accumulated characters inserted by i1
    int s2 = 0;     // Accumulated characters inserted by i2
    while(i1 && i2)
    {
        int d = (s1 + i2->q) - (s2 + i1->q);
        if (d < 0 || d == 0 && i2->s < i1->s)
        {
            // Process i2
            i2->q += s1;
            s2 += i2->str.size();
            i2 = i2->next;
        }
        else
        {
            // Process i1
            i1->q += s2;
            s1 += i1->str.size();
            i1 = i1->next;
        }
    }
    if (s1)
    {
        while (i2)
        {
            i2->q += s1;
            i2 = i2->next;
        }
    }
    if (s2)
    {
        while (i1)
        {
            i1->q += s2;
            i1 = i1->next;
        }
    }
}

However this algorithm is incompatible with the MP3 property [2]. The following example illustrates the problem:

Let there be three sites with siteids satisfying S₀ < S₁ < S₂. Initially all sites have an empty text field. The following steps are performed.

S₀ generates local operation O₀ = S₀: insert “00”.
S₁ generates local operation O₁ = S₁: insert “1”.
S₂ receives O₀ from S₀, and inserts “00”.
S₂ generates local operation O₂ = S₂: insert “2”, to get “020”.
S₂ receives O₁ from S₁, and calculates v = v_out(S₁.hb) ↓ v_out(S₂.hb) = (0,1,0) ↓ (1,0,1) = (0,0,0). S₂ factorises its HB according to v = (0,0,0), so Lf = “”, Rf = “020”. It then merges “1” to yield “0120” which is wrong—it should have got “0201”. The reason is that “1” must come after “00”.

Note that O₁ || O₀ and O₁ || O₂, so we have merged two concurrent R-factors. Evidently rule MP3 is broken:

(MP3) IT(O₁, O₀ ⊕ O₂) = IT(O₁, [O₀, O₂])

The problem is associated with how to correctly IT past the merge of O₀,O₂ where O₀ → O₂.

Editorial note: The following retrospective review was added to the website and is not part of the archived paper.

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 arbitrarily 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 siteid 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 by [4]

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 [2]).

Previous21.2 Composite operations on bags based on deltas Next21.4 Siteid inheritance