41 Bags

Composite operations on bags based on deltas

Let the document state consist of a single field of type bag<T>. Consider that for each possible k∈T, c_k denotes the number of elements in the bag with value k. In other words c_k is the multiplicity of k.

Consider furthermore that an operations on the bag to insert an element with value k is regarded as applying an offset of +1 to c_k. Similarly an operation that removes an element with value k is regarded as an offset of -1 to c_k.

The nice thing about this approach is that the solution for deltas is directly appropriate and we know that this solution is very efficient (and of course ensures that all sites converge).

We would like to enforce the constraint that c_k cannot become negative. However concurrent removals from a bag can certainly lead to that. Even worse, consider the case where initially the bag has one element and concurrently site S₁ removes the element, site S₂ also removes the element and site S₃ inserts an element. Then the solution based on deltas results in c_k = 0 - ie the bag is empty which is probably not very sensible because S₁,S₂ were able to remove an element that they never knew about!

TODO: Investigate a solution which is compatible with conservation of matter and without negative amounts appearing.

Deletes that identify the element they are deleting

Consider that we pretend the elements of the bag have identity according to the (s,t) of the operation that inserted that element. By accounting for identity in this way we can ensure that a delete operation is only able to delete elements that causally preceded it.

So for given k an operation records a set I_k of (s,t) insertions and a set D_k of (s,t) deletions. These two sets are independently managed using delta semantics based on set union. Both of these sets can only increase over time. Note that when we generate a delete operation it is important to distinguish the (s,t) assigned to it as an atomic operation versus the (s,t) used to identify the element being removed.

It is straightforward to calculate the set difference P_k = I_k\D_k. We define the multiplicity of k in the bag to be c_k = |P_k|. Note by this approach we never get c_k < 0. Also deletes can never dominate concurrent insertions.

This approach can also be used for sets, by defining presence in the set by the condition c_k > 0.

Implementation

We store a map keyed by k. This takes us to a map keyed by s. This takes us to

1. a set of enabled insertions recorded as an ordered list of t values.
2. a set of disabled insertions recorded as an ordered list of t values.
3. a set of deletions recorded as a set of (t,si,ti) triples, where t is the sequence number assigned to the deletion as an atomic operation and (si,ti) identified the insertion being deleted.

The distinction between enabled and disabled insertions is a caching concern that is only relevant to an operation with v_in = {}. We want to wangle it do that when we merge a remote op into the local HB we don't actually need to re-enable an insertion when we calculate the LFactor. Arguably factorisation shouldn't be separated out from concurrent merge.

When an operation is to be merged, we basically want to apply the new deletions. This should be quite fast if we use binary search amongst the remaining enabled insertions. That allows these insertions to be moved over to the deleted pile. This is where we decrement c_k.

When calculating an RFactor to be sent over the wire we don't distinguish between enabled/disabled insertions. As far as we're concerned we're sending the whole lot.

Problem

A problem with this approach: What happens when the bag is initially non-empty? How do we record the deletes? Note that when an interactive collaboration begins relative to some defined base vector time we will certainly have nonempty bags.