Tavistock
commented
9 years ago 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.
( 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.