64 Siteid comparison fails on composite insertions

Status: This chapter records exploratory or unsuccessful design work and is retained for historical reference.

In the following we explain why the Dual IT algorithm that works on multi-character atomic operations doesn't work on composite operations.

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 vin and vout
  • A vector<Entry> ordered by insertion position, that are specified in post insertion coords. 

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)
{
}

Proposed Dual IT algorithm

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

Let O1 <> O2. The dual IT of O1,O2 involves simultaneous left to right scans through both O1 and O2 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 O1. Similarly we have a counter for O2. In order to compare the positions of the next interval from O1 and the next from O2, we must offset the interval from O1 to the right by the number of insertions by O2. Similarly we must offset the interval from O2 by the number of insertions by O1.

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;
        }
    }
}

But MP3 isn't satisfied

Unfortunately this simple approach doesn't work. It is not possible in general to merge composite operation RFactors using simple left to right scans through the insertion intervals, using siteid comparisons to resolve the order of coincident insertions.

Indeed this algorithm is incompatible with property MP3:

IT(O1, O2 ⊕ O3) = IT(O1, [O2, O3])

(see Operational transform Merging operations).

The following example illustrates the problem: Let there be three sites with siteids satisfying S0 < S1 < S2. This total order on the site ids also gives the order on concurrent insertions of text at the same position. Initially all sites have an empty text field. The following steps are performed.

  1. S0 generates local operation O0 = S0: insert "00"
  2. S1 generates local operation O1 = S1: insert "1"
  3. S2 receives O0 from S0, and inserts "00"
  4. S2 generates local operation O2 = S2: insert "2", to get "020"
  5. S2 receives O1 from S1, and calculates v = vout(S1.hb) ↓ vout(S2 .hb) = (0,1,0) ↓ (1,0,1) = (0,0,0). S2 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 O1 || O0 and O1 || O2 , so we have merged two concurrent R-factors. Evidently rule MP3 is broken:

IT(O1, O0 ⊕ O2) = IT(O1, [O0, O2])

The problem is associated with how to correctly IT past the merge of O0,O2 where O0 → O2. 

    Consider three sites S0,S1,S2 where the initial document state is empty, which we denote by [].

        S0 inserts "00" to give [00].
        S1 inserts "1" to give [1]
        S2 receives O0 then inserts "2" in the middle to give [020], then receives O1 to give [0201]

    The hard part is to make sure S2 ends up with [0201] not [0120].  We use the idea of effective
    site ids.

    Site S0
    -------
        initial         []
        generates O0    [00]

    Site S1
    -------
        initial         []
        generates O1    [1]

    Site S2
    -------
        initial         []
        receive O0      [00]
        generates O2    [020]
        receive O1      [0201]