29 Quadratic complexity

In Operational transform Control Algorithm the HB suffix is a per session transient linear sequence of atomic operations, and dual IT is used to transform incoming operations against the HB suffix. Unfortunately this becomes inefficient when the suffix becomes very large - eg when there has been a temporary network outage. Basically the problem is the quadratic order complexity of transforming a list against a list. For example if two sites have performed 10000 operations then the number of transformations required for their reconciliation is 100 million which is prohibitive.

Calculating a transient HB suffix

Given a local site HB with vector time vhb, and a remote operation with execution context described by vector time v, there is a need to calculate the initial HB suffix โ€“ which consists of all the operations in ๐œ’(vhb)\๐œ’(v). In [1] this involves:

  1. Initialising the HB suffix by copying the tail of the persistent HB, beginning with the left most operation that is outside ๐œ’(v).
  2. Taking the transpose of adjacent operations in the HB suffix in order to move operations outside ๐œ’(v) to the right of operations that are inside ๐œ’(v).
  3. Popping (ie removing) a prefix consisting of the operations inside ๐œ’(v) from the HB-suffix.

The combination of steps 2 and 3 is called a transpose and pop.

Step 2 can be computationally expensive. The most expensive case occurs when there are a large number n1 of operations outside ๐œ’(v) to the left of a large number n2 of operations that are inside ๐œ’(v). The cost of transposing is O(n1 n2).

This can readily occur in practice. For example, let there be three sites S1,S2,S3. In the diagram below, assume that S1 connects to S3 only after S1 has already appended lists L1 then L2โ€™ to its local HB. When S1 connects to S3 and receives O3 it will need to transpose L1 and L2โ€™ in order to calculate an appropriate HB suffix to transform O3. This could be expensive if L1 and L2 have many atomic operations.

Steps 2,3 are also repeatedly applied during the session in order to bring the existing transient HB-suffix up to date as the execution context of received remote operations grows over time. Again, step 2 can be computationally expensive. Consider the same diagram again, now assuming that S1 and S3 had established a connection from the very beginning. At the time S1 receives O3 from S3, S1 will have already appended L1 then L2โ€™ to its transient HB suffix for its session with S3. The execution context of O3 shows that transpose of L1 and L2โ€™ will be required on its transient HB suffix.