42 Sets

Let the document state be a set over some element type T. T is a value type, and is assumed to support an equality comparison operation.

We require a solution to the operational transform of the following two operations used to update the set:

ins(v) - insert value v into the set (if not present)
del(v) - delete value v from the set (if present)

Both of these operations are idempotent.

Note the following:

∀v,w ∈ T, ins(v) and ins(w) commute, because (S∪{v})∪{w}=(S∪{w})∪{v}.
∀v,w ∈ T, del(v) and del(w) commute, because (S\{v})\{w}=(S\{w})\{v}.
∀v,w ∈ T, v≠w ⇒ ins(v) and del(w) commute, because (S∪{v})\{w}=(S\{w})∪{v}.

Note however that ins(v) and del(v) don't commute.

1. Solution using a disable count for each element of T (August 2005)

In August 2005 Operational transform - Set theoretic operations proposed that a delete operation be disabled (using a disable count) when it IT's past an insert operation of the same value, so at quiescence all sites agree that the value was inserted.

There are two issues:

No proof of correctness of using a disable count was given (i.e. that satisfies TP1 and TP2).
Even if this solution allows for IT/ET on atomic operations, a solution using composite operations and taking and applying an RFactor isn't discussed.

2. Solution using boolean assignment operations for each element of T

Each key is (conceptually) mapped to an assignable boolean variable for whether the key is a member of the set. Conflicts are resolved using the dominance relation on vdoms.

This approach can be implemented by AssignOps since a FieldId has a path and a path includes the key into a set. It is a matter of dealing specially with sets when navigating a path. A boolean is sent over the wire when sending an operation, but the boolean is stored implicitly according to whether the key is in the set.

A downside is that concurrent deletes can dominate inserts. For example in the following scenario, after merging it is possible that v is not present in the set:

    Initially v is not present
    User 1 : ins(v)
    User 2 : ins(v) then del(v)

3. Solution using an offsetable integer counter for each element of T

This is a proposal that takes advantage of the very efficient support for offset operations on integer variables. For each key there is an integer counter. A key is deemed to be present in the set if and only if its counter is positive. An insertion is performed by applying an offset of +1 to the counter. A deletion is performed by applying a negative offset to the counter to bring it down to zero.

Unfortunately as pointed out in Composite set operations 4, this solution doesn't work reasonably, it allows sites to inadvertently delete concurrently inserted elements.

4. Solution using two "vector times" for each element of T

This solution has been unit tested successfuly in OpTransTest. See CompSetOp3.cpp. It basically involves storage of two "vector times" for each v∈T. The scare quotes are because the vector times are not intended to represent causally valid database states, but rather only a way to define certain sets of atomic operations.

For each v∈T of a field of type set<T>:

Let:

I = { (s,t) | op(s,t) inserted v into the field }
D = { (s,t) | (O₁ = op(s,t) inserted v into the field) AND (∃ O₂ such that O₁→O₂ and O₂ deleted v from the field) }

Once we insert (s,t) into I we never remove it from I. Therefore I is a monotone increasing set over time. When merging all the operations from two sites we take the union of the I's to give the merged I.

Similarly D is a monotone increasing set over time, and when merging all the operations from two sites we take the union of the D's to give the merged D.

We don't record these monotone increasing sets in a composite operation because that could be expensive. Instead we record two "vector times" i and d defined as follows:

i: the smallest vector time containing I
d: the smallest vector time containing D

Each site uses i,d to calculate the field: (v ∉ field) ⇔ (i ≤ d) ⇔ (X(i) ⊆ X(d)) ⇔ (I ⊆ D)

Merging composite operations involves the 'max'' operation on the vector times i and d:

(O1⊕O2).i = O1.i ↑ O2.i
(O1⊕O2).d = O1.d ↑ O2.d

Unfortunately it is not well tailored to efficiently finding an RFactor. 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.

5. Solution using set of (si,ti) or (si,ti,sd,td) for each element of T

See Composite set operations for the original description. This idea seems promising and an implementation was started in cxOperation (see class SetOps). However it is not completed, instead solution 2 using assignment operations is currently used.

For each v∈T for a field of type set<T>:

Let:

I = { (si,ti) | op(si,ti) inserted v into the field }
D = { (si,ti,sd,td) |
op(si,ti) inserted v into the field AND
op(sd,td) deleted v from the field AND
op(si,ti) → op(sd,td) }

It is assumed v is in the field if there exists an operation that inserted it for which there is no causally proceeding operation that deleted it.

v ∈ field
⇔ (∃ O₁ such that O₁ inserted v) and (O₂ deleted v ⇒ not( O₁ → O₂) )
⇔ ∃(si,ti) ∈ I, ∄ (si,ti,sd,td) ∈ D

Once we insert (si,ti) into I we never remove it from I. Therefore I is a monotone increasing set over time. If we recorded I at each site then when merging the operations from two sites we would take the union of the I's to give the merged I.

I₁⊕I₂ = I₁ ∪ I₂

Similarly D is a monotone increasing set over time, and if we recorded D at each site then when merging the operations from two sites we would take the union of the D's to give the merged D.

D₁⊕D₂ = D₁ ∪ D₂

However we don't record these monotone increasing sets in a composite operation because that could be expensive. Fortunately we can safely remove redundant information from I and D.

If site si inserts v into the field multiple times then only the last operation matters. So if (si,ti) ∈ I has the largest ti for that si, then we don't retain records in I and D with a smaller ti for that si.
In D, if there are multiple (sd,td) for a given (si,ti) then it is sufficient to only record one of the (sd,td). So each site retains the first (sd,td) it sees, and any extra (sd,td) for the same (si,ti) are discarded.
If (si,ti,sd,td) ∈ D then there is no need to retain the corresponding (si,ti) ∈ I.

We can record sufficient information in a single map from site identifier si to an algebraic data type K defined as follows:

type K = e
       | i(ti)
       | d(ti,sd,td)

e means the value has never been inserted by site si
i(ti) means the value was inserted by op(si,ti) and there is no causally proceeding operation that deleted it
d(ti,sd,td) means the value was inserted by op(si,ti) and deleted by op(sd,td) and op(si,ti) → op(sd,td)

In an actual implementation, the "empty" value e corresponds to not recording a (key,value) pair in the map.

The merge of two maps is defined in terms of the merge of two values of K. The following table shows how values of K are merged

k1	k2	k1⊕k2
e	k2	k2
k1	e	k1
i(ti1)	i(ti2)	i(ti1) if ti1>ti2 else i(ti2)
i(ti1)	d(ti2,sd2,td2)	i(ti1) if ti1>ti2 else d(ti2,sd2,td2)
d(ti1,sd1,td1)	i(ti2)	i(ti2) if ti2>ti1 else d(ti1,sd1,td1)
d(ti1,sd1,td1)	d(ti2,sd2,td2)	d(ti1,sd1,td1) if ti1>ti2 else d(ti2,sd2,td2)

To calculate an RFactor with respect to some vector time we find the restriction of the map where:

si ↦ i(ti) is in the RFactor if (si,ti) is outside the extent of the vector time
si ↦ d(ti,sd,td) is in the RFactor if (sd,td) is outside the extent of the vector time.

SetOps.h in cxOT

Source: Ceda/cxOT/SetOps.h

TestSets.cpp in txOT

Although the purpose of this test is to validate OT on a field of type set<T> we only test on a boolean field. At quiescence all sites must agree on the value of the boolean. This provides a basis for OT on a field of type set<T> by interpreting the boolean state as the condition of whether a given value of T is in the set.

Note that the test is simplistic in the sense that it doesn't model the delay between sending and receiving an RFactor.

Source: CedaTests/txOT/src/TestSets.cpp

Output of test

Unit test set operations
    RunTest : time=60.0001s  sites=2  numLocalOps=70792177  numSendOp=70812802 numCheckCgce=35405021
    RunTest : time=60s  sites=3  numLocalOps=63433568  numSendOp=63455039 numCheckCgce=31726193
    RunTest : time=60.0001s  sites=4  numLocalOps=49932692  numSendOp=49958288 numCheckCgce=24974620
    RunTest : time=60.0001s  sites=5  numLocalOps=44805581  numSendOp=44823961 numCheckCgce=22407458
    RunTest : time=60.0001s  sites=6  numLocalOps=41219700  numSendOp=41231586 numCheckCgce=20612914
    RunTest : time=60s  sites=7  numLocalOps=37583512  numSendOp=37593413 numCheckCgce=18793275
    RunTest : time=60.0001s  sites=8  numLocalOps=32887913  numSendOp=32898176 numCheckCgce=16444111
    RunTest : time=60.0001s  sites=9  numLocalOps=31097448  numSendOp=31106800 numCheckCgce=15548952

Previous41 Bags Next43 Composite set operations 4