15.6 Set operations

(30 Aug 2005)

Abstract

This paper provides a solution to the operational transform of set theoretic operations.

Introduction

The document state is assumed to be a set over some element type T. T is a value type, and is assumed to support an equality comparison operator. In this paper we study the operational transform of the following set theoretic operations:

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

Each of these operations is idempotent.

We need convergence at quiescence even though operations are executed in different orders at different sites. Specifically, we require properties TP1 and TP2 [1].

Properties required to achieve convergence

TP1

∀ O1, O2, S + [O1, IT(O2, O1)] = S + [O2, IT(O1, O2)]

TP2

∀ O1, O2, O3, IT(IT(O3, O1), IT(O2, O1)) = IT(IT(O3, O2), IT(O1, O2))

Discussion

In the following cases, let O1, O2 be concurrent operations that are performed on the same document state S.

ins(v1) and ins(v2) commute

Let operation O1 insert value v1, and let O2 insert value v2. The set-theoretic union operation is associative and commutative; therefore,

(S ∪ {v1}) ∪ {v2} = (S ∪ {v2}) ∪ {v1}.

Hence operations O1, O2 commute and therefore nothing needs to be done under IT.

del(v1) and del(v2) commute

Let operation O1 delete value v1, and let O2 delete value v2. According to set theory

(S \ {v1}) \ {v2} = (S \ {v2}) \ {v1}.

Hence operations O1, O2 commute and therefore nothing needs to be done under IT.

ins(v1) and del(v2) commute when v1 ≠ v2

Let operation O1 insert value v1, and let O2 delete value v2. If v1 ≠ v2 then:

(S ∪ {v1}) \ {v2} = (S \ {v2}) ∪ {v1}.

Hence operations O1, O2 commute and therefore nothing needs to be done under IT.

ins(v) and del(v) do not commute

The only difficult case is where O1 inserts value v, and O2 deletes value v. It is proposed that we disable a delete operation when it is inclusion-transformed past an insert operation of the same value, so at quiescence all sites agree that the value was inserted.

This is implemented using a disable count, so that a delete operation may be disabled multiple times as it is inclusion-transformed past a number of insert operations. Under ET, the delete operation will only be re-enabled when it has been exclusion-transformed backward past all the insert operations that caused it to be disabled.

Solution

Let an operation contain the following fields: 

struct SetOp
{
    bool ins;
    int dc;
    T v;
};
Field Description
ins Boolean flag to indicate whether this is an insert or delete operation
dc Disable count, only relevant to a delete operation. Initialised to zero when the operation is first generated
v Value to be inserted or deleted

The following C++ code shows the implementation of IT/ET 

void IT(SetOp& O1, const SetOp& O2)
{
    if (O2.ins && !O1.ins && O1.v == O2.v) ++O1.dc;
}
void ET(SetOp& O1, const SetOp& O2)
{
    if (O2.ins && !O1.ins && O1.v == O2.v) --O1.dc;
}

Future work

  1. In order to support undo it is necessary to flag whether an operation actually inserted or deleted a value. This flag must undergo transformation under IT/ET
  2. For performance this solution should be extended to support operations that insert or delete multiple elements at once. This also allows for operations to be closed under merging. Furthermore it will be possible to compress merged operations by eliminating elements that are inserted then deleted by the operation. Compression can also discard disabled delete operations.

Tests

Simulation of multiple sites

Each simulation creates between two and nine sites, all starting with the same database of set fields. The state at each site is represented by: 

using VectorTime = std::vector<int>;  // Indexed by SiteId

struct Site
{
    SiteId id;
    Database database;
    VectorTime time;
    std::vector<SetOp> history;
};

The vector time records how many operations originating at each site have been applied. The history contains every local or received operation applied at the site, in a causally valid linear order.

Generating an operation

A randomly selected site generates an operation against its current state. The operation selects a random set field and a random value, and then either inserts or deletes that value. It is applied locally, appended to the site's history, and recorded in the site's vector time.

Sending an operation

To send an operation, the simulation selects the first operation in the sender's history that the receiver has not applied. The preceding operations in the sender's history define its causal context. The receiver performs the Factorise step described in 8 Operational Transform Control Algorithms, using Transpose to rearrange its history into a prefix containing that context and a suffix containing operations concurrent with the incoming operation. It then applies IT to the incoming operation for each operation in the concurrent suffix before applying it to the receiver's database. This exercises IT, ET and Transpose as operations arrive in different causally valid orders.

Checking convergence

Simulation events randomly generate an operation, send one operation between two sites, or fully synchronise a pair of sites. A synchronised pair must have equal vector times and equal databases. After the final event, all outstanding operations are exchanged and the same comparison is made across all sites.

After every event, the test also checks that the number of operations in each site's history equals the sum of its vector-time components and that no operation has a negative disable count.

Results

A total of 30,000 simulations of 500 events each completed without a convergence failure.

Browse the test files.

References

  1. David Barrett-Lennard, Operational Transform — Control Algorithm, August 2005.