Commutative Replicated Data Type Notes

The Move Problem

Using the notation of the "Data Consistency for P2P Collaborative Editing", I'd like to explore the issue of moving steps within a sequence. Assume there are hidden step ids marking the start, α, and end, ω. Normal sequence steps have ids represented by English alphabet characters a, b, c, etc. Assume both peers begin with a three step sequence:

α a b c ω

A move could be represented as a series of two primitive operations: del followed by ins. For example, to move b to the start we could:

del(b)
ins(α ≺ bʹ ≺ a)

We have to come up with a new id for step b, since past edits may refer to it and its relative position between steps cannot change. The id bʹ represents the same step b but in a new location. We end up with

α bʹ a -b- c ω

where -b- represents a hidden/deleted step. Of course a different peer starting with the same initial sequence could simultaneously move b to the end of the sequence with

del(b)
ins(c ≺ bʹʹ ≺ ω)

Resulting in the sequence

α a -b- c bʹʹ ω

When all operations have propagated and been applied to both peers we would then eventually have

α bʹ a -b- c bʹʹ ω

It is unclear to me that this is intention preserving, though perhaps an argument could be made. Certainly if a, b, and c were characters in a text document this might not be unreasonable. The user isn't thinking in terms of "moving" b around in the document but rather in deleting and inserting which is as easy as retyping a character. For sequence steps, which are themselves made up of many properties, the UI should make rearrangement easy. It seems like one logical move or the other should "win".

At any rate, undo complicates the situation. For undo we can use an effect counter like the one detailed in "Scalable XML Collaborative Editing with Undo". If move is comprised of two primitive operations though, somehow we have to track that undoing a move has to undo both primitive operations.

I think this may mean that we need a new primitive, move. A move would track the original step id, and the new step id with its previous and next insertion point. Two conflicting moves would have to pick a winner and the loser would have to effectively undo its move to apply the winning move.