44 Composite set operations

Currently the most likely solution has been unit tested successfuly in OpTransTest. See CompSetOp3.cpp

For each key of a field of type set<Key> we record:

  • i: the smallest vector time containing the set of (s,t) for all insertions of that key that have ever occurred
  • d: the smallest vector time containing the set of (s,t) for all insertions of that key that have been masked or dominated by some deletion.

The key is not present if and only if i <= d. (i <= d means i is a subset of d)

(O1+O2).i = O1.i union O2.i
(O1+O2).d = O1.d union O2.d

It basically involves storage of two vector times per key.

Sending a delta

Unfortunately it is not well tailored to efficiently finding a delta.

Presumably most of the problem can be solved using transient state. This could basically record the keys that have been inserted or deleted since the last delta was sent.

However that doesn't help for sending the very first delta in an interactive session.

An alternative approach is to simply use assignment semantics. i.e. each key is mapped to an assignable boolean. The only downside is that deletes can dominate inserts.

todo: Investigate an idea to record redundant partial information to narrow down the search. E.g. record keys as a function of (s,t). This is historical information but not intended for use by OT. Instead only used to help send a delta.

Bags

For a given key, consider that we record the set of (s,t) for insertions that haven't been deleted. The cardinality of this set gives the number of repeated key values in the bag.

This set is recorded as follows: 

    fid --> key --> s --> vector
                       (inserted t values)

Note that the (s,t) that have been deleted is implicitly recorded! 

Insert:         simply add additional (s,t) as required
Get delta :     simply send (s,t) outside rhv
Merge delta :

Sets 2

It makes sense to deal with each key independently. For each key we need to agree on a bool - is it present or isn't it?

A key is present on a site iff exists insertion operation Oi applied on the site that inserted it and there doesn't exist a deletion operation Od applied on the site such that Oi --> Od.

For a given site s, s may have inserted the key. It is sufficient to only record the last t of the insertion. (all earlier t's for insertions are redundant).

insert: (s,t) - largest t of insertion by s.

Now consider that this t has been made redundant. How can we mark it so?

Sending a delta 2

1)
    For each s, store (s,ti,td) where:

        ti = largest t for which (s,ti) inserted the key
        td = largest t for which (s,td) inserted the key, but the key was causally deleted
             afterwards

    Given rhv, we send information as follows:

        (s,t) outside X(rhv) =>  must send (s,ti)
        ? how know when to send (s,td) - haven't recorded when the delete occurred.

2)
    For each s, store (s,ti,sd,td) where:

        (s,ti) - last operation that performed insertion of the key by site s
        (sd,td) - if present then this operation deleted the key and masked (s,ti).
                  (it doesn't matter which delete we record if this is ambiguous)

    Key Present if :  exists (s,ti,sd,td) where (sd,td) not present.

    Send if :  (s,ti) outside X(rhv) or
               (sd,td) present and (sd,td) outside X(rhv)

    Merge:   for each s,  replace quadruple of O1 with O2 if

               O2.ti > O1.ti or
               (
                    O2.ti == O1.ti &
                    O1.(sd,td) not present &
                    O2.(sd,td) present
               )