3

I’m a little unclear on some questions relating to the "intent" part of concurrent collaboration algorithms (operational transformation and conflict-free replicated data types). Please help!

  1. Strings are a frequently used example in OT explanations. Usually, you see something like "abd" * ins('c', 2) * del(1) ≠ "abd" * del(1) * ins('c', 2) — which resolves to "acd" ≠ "adc". Hence, you might transform the second ins('c', 2) into ins('c', 1) based on the delete. However, there seems to be an implicit assumption in the setup here — namely, that the insertion point should be shifted along with the other characters in the string. What if you were instead drawing some ASCII art, intending for each character to be at a precise column marker? In that (less common) case, the transform would be completely different! Or — what if you were using the text editor as a rudimentary counter, adding and deleting tick marks from a long string along the lines of "||||||||" (for whatever bizarre reason)? Normally, a concurrent delete operation on the same character in two clients would merge into one, but in this odd use case, both deletes would need to propagate. Neither one of these alternate use cases is implicitly built into the definition of a string, which (as a simple array of characters) is quite flexible. Specifying this behavior is absolutely essential to getting concurrent collaboration working as expected! But I'm a bit confused: is this property the same thing as "intent", as defined by the CCI model? This is what I figured at first, but skimming the original Ellis and Gibbs OT paper, it seems that intent features pretty heavily in there as well (even though it's not explicitly called out as such). If this is indeed the case, what exactly differentiates CC from CCI?

  2. So, if I'm thinking about this problem right, it seems that the key to successful real-time collaboration is ensuring that changes from each client a) eventually converge, and b) reflect the original intent as much as possible. But! With the usual approaches, intent is either deeply embedded in tangled webs of transformation functions (with OT) or rigid data structure definitions (with CRDTs). It's also very local, often operating in the realm of single-character modifications instead of a wider context. Given how important specifying intent is (as demonstrated above), wouldn't it be nice to just have a single, linear block of code that deals with intent? With this in mind, it seems that Neil Fraser's differential synchronization approach — basically, sending partial diffs around until everyone converges — is the best one of all. Sure, it's a little heavyweight and lacks the mathematical elegance, but at least the intent (via the diff + fuzzy patch algorithm) is localized to just one easily-editable spot of code, not emergent out of the transformation/control functions or data structures. And yet, diff sync is almost entirely ignored by the community, except as an occasional introductory slide to an OT/CRDT lecture. Why is this? Admittedly, fuzzy patching cannot guarantee to cleanly resolve all conflicts, especially if enough context is clobbered, but the other two approaches each have their own failure modes — automatically resolving to nonsense without any way out, trapped in a mathematical lattice. At least with fuzzy patching, you always have the option to just append a gnarly change to the end of the sentence/paragraph/document prefixed by "MERGEME", neither losing nor corrupting any data. (Hopefully very rarely!) And in exchange, you get immense flexibility and clarity in specifying your intent! You also no longer need to think about sync in terms of single operations, allowing you to expand and alter your model editing vocabulary completely independently of the sync system (as long as your diff function is reasonably clever). Is this accurate? If so, why is diff sync so rarely used?

  3. Reading this article on Clear's OT-inspired merge, it seems that you can create a dead-simple, OT-esque system by a) defining your data model as the end result of your operation history played back in sequence (and keeping the entire history around), b) defining a total order with Lamport timestamps and resolving concurrent operations via device UUID, and c) re-sorting the history whenever a new operation comes in out-of-order. (So — no transforms.) In terms of "natural" string editing, intent would be clobbered… but the whole thing would still converge! Perfectly fine for certain use cases if you define your data structures and operations appropriately. So why is this baby example almost never brought up, even as a starting point? Is it because OT is assumed to mutate the model instead of appending operations to a comprehensive history log? Or is there some fundamental flaw? I feel like this "rebase history" approach (as opposed to "merge history" with regular old OT) is veering into the territory of CRDTs... but I'm not sure. Am I on the right track here?

Thank you! Apologies if there are basic errors and fundamental misunderstandings hiding in these questions: I've only started looking into this a few days ago.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.