Constraints ⇒ OT is intractable

Much of the literature on Operational Transformation is concerned with finding inclusion transforms that satisfy properties TP1 and TP2, which are needed to ensure all sites converge at quiescence. See this primer on Operational Transformation

It is not easy, indeed there have been many examples of erroneous algorithms, one research group proposed using automated theorem provers to validate the solutions. See Proving correctness of transformation functions in collaborative editing systems by Gérald Oster, Pascal Urso, Pascal Molli and Abdessamad Imine (2005).

The CEDA merge algorithms allow for arbitrary merging of changes to text.

The result is of a merge is always defined, and it is always the union of all the insertions minus the union of all the deletions. The relative order of the inserted characters is always maintained when merging operations.

This seems like a simple case, and yet there are multiple papers in the literature with incorrect algorithms - because of the TP2 puzzles which are only apparent when there are at least three sites.

In this case the only constraint is that the characters are ordered.

Now consider that we impose a much more complex constraint, say that the string is a valid Java program according to the Java language specification (e.g. it much conform to the grammar).

It is difficult (impossible?) to ensure that in general the merge of arbitrary concurrent operations will satisfy such a constraint.