Practical Intro to Operational Transformation

Summary

Practical Intro to Operational Transformation Can’t you just give me the best algorithm? Table of Contents What’s OT & CRDT OT vs CRDT Intro to OT TP1 and TP2 Control algorithm Undo A simple OT algorithm Real world implementations Appendix A, OT vs CRDT cont. Appendix B, OT history Resources Unfortunately, there isn’t a single best algorithm that you can just learn and implement. There are many different algorithms, each with their own trade-offs and subtleties, none of which I found completely satisfactory. In this article, I hope to just introduce basic ot concepts in simple terms, and draw a rough picture of how it generally works, and point readers to materials for further reading. I also included a simple ot algorithm that should give the reader something concrete to look at. A huge disclaimer upfront: I’m not an expert, only someone that read all of papers and blog posts that I can find, so take what I say with a grain of salt. There’s a frustrating lack of materials of ot online (which is part of what prompted this article), so I can’t say I’ve grasped the whole picture regarding ot. If there’s any mistake, or anything I missed, please do let me know. Thanks! What’s OT & CRDT Nowadays you can’t talk about ot (operational transformation) without mentioning crdt (conflict-free replicated data types). Broadly speaking, they are the two approaches to collaborative editing. ot is the first to be conceived and researched on since the 90’s. crdt is a database/distributed system concept that was brought into collaborative editing in around 2006. I’ll briefly introduce both and give them a comparison, before delving into ot. ot works by transforming operations like insert, delete, update, etc. Consider this example: Two users A, B work on a document containing only “x”; A inserts “a” before “x” (insert “a” at position 0), propagates its operation to B; Not yet aware of A’s modification, B deletes “x” (delete at position 0), propagates its operation to A. Now if A appl...