43 Composite set operations 4

(this relates to the implementation in CompSetOp4.cpp of OpTransTest. See CompSetOp4.cpp)

We have a solution for deltas on an ssize_t field that is very efficient. It involves recording

    s --> t,o       (s,t) - the last operation that applied an offset
                      o   - the total offset applied by that site.

    insert(s,t,o)
    {
        O[s].t = t;
        O[s].o += o;
    }

    getdelta(rhv)
    {
        for each s
            if (O[s].t >= rhv(s)) d[s] = O[s]
    }

    merge(d)
    {
        tot = 0;
        for each s in d
        {
            if (d[s].t > O[s].t)
            {
                tot += d[s].o - O[s].o;
                O[s].o = d[s].o;
            }
        }
    }

Let

    ni: cardinality of the set of (s,t) for all insertions of that key that have ever occurred

    nd: cardinality of the set of (s,t) for all insertions of that key that have been
        causally masked or dominated by some deletion.

Consider that we use this solution to record x = ni-nd.

So for each local

    insertion we apply delta +1 to x
    deletion we apply  delta -x to x (so it becomes zero)

So space required is:

    fid --> key -->  s  -->  (t,o)
                     x

Note that the total offset o applied by a given site can be negative!

Problem

This solution breaks our requirements for intention preservation, because it allows sites to inadvertently delete concurrently inserted elements.

Example with two sites.

    S1:  insert                     +1
    S0:  receive insert from S1
    S1:  delete                     -1
    S0:  delete                     -1
    S1:  receive delete from S0  --> x = -1