LSEQ + Tombstones

[Chat-Wane]

( Follow up of the discussion from issue #10 )

LSEQ, Logoot, Treedoc do not require tombstones (although the latter is hybrid). They need some sort of causality tracking mechanism that will track the special case of "insert an element and delete this element" which does not commute. They also need to know if a particular element is not inside the data structure because it is not arrived yet, or because it has been deleted (to avoid insert(e); delete(e); insert(e)).

So you have Network -> Causality Tracking -> CRDT (-> Editor )

You could use tombstones, but the complexity in space is not great and cannot be safely garbage collected. The causality tracking mechanisms (such as version vectors, interval version vectors, or version vectors with exceptions) allows compressing the tombstones in their structure. Their complexity depends of the number of team members actively collaborating instead of the number of insertions in the structure.

The fundamental difference between CRDTs with and without tombstones is that the former's identifiers do not require deleted elements to be totally ordered while the latter's identifiers do.

[Tavistock]

Ok so maybe tombstones is not the correct word. It would just be node that instead of being deleted you would make it's element be a special object (in clojure's case a keyword (I'd name it something like ":del") which is like an atom in erlang, idk what you would use in js).

This new structure would not be garbage collectible and would grow over time but it would only be used to transmit change. You would call the new merge function like this merge(my_tree, others_tree_plus_deletes). I would not store the new LSEQ to represent my document I would create one to send over the wire to another persons LSEQ.

The new LSEQ would be to store deletes.

[Tavistock]

I'm wrong. I will explain the problem better later.

[Tavistock]

So I think my idea of lseq+tombstones might decrease the overhead of messages, but it also might not. My thinking was that getting the merge operation for lseq would make it costly for remote merges and surely this could be reduced (you would have to send your whole local copy to a remote consumer). It is just sort of me prematurely optimizing. I will try to get merge to work on my version of lseq and then see if it needs a second merge (transit optimized merge). But then again "working is better than perfect" so I have a lot to do before I get to merge and optimizing said merge.