22.2 Composite set operations 4

(8–14 July 2009; transcribed from source comments in December 2021)

This relates to the implementation in CompSetOp4.cpp of OpTransTest.

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

Source code

The complete sequence of four composite-set experiments is retained at Subversion revision 620, dated 14 July 2009. This snapshot shows the rejected approaches as well as the implementations discussed in these subchapters. Browse the July 2009 source files.