Dispelling Misconceptions and Unveiling the Truth about GOT and OT in General
To recap, my first post titled "What's Wrong with 'The Art of the Fugue' Paper about OT (adOPTed)?" (https://news.ycombinator.com/item?id=36208585) presented a comprehensive analysis showcasing the consistent and non-interleaving outcomes delivered by the adOPTed algorithm, thereby refuting the alleged "char-interleaving" problem. Moreover, I revealed a fundamental flaw in the Fugue paper's portrayal of the adOPTed algorithm—it mistakenly presented a flawed dOPT-like algorithm instead of the authentic adOPTed algorithm, disregarding the resolution of the well-known dOPT-puzzle. It is disheartening to witness the perpetuation of the dOPT-puzzle within the pages of the Fugue paper, despite its long-standing resolution.
In my second post titled "Unveiling Issues with 'The Art of the Fugue' Paper Regarding Jupiter-OT" (https://news.ycombinator.com/item?id=36415068), I provided a comprehensive explanation of why Jupiter-OT consistently produces non-interleaving outcomes, irrespective of whether it is utilized with string-wise or char-wise transformation functions. This effectively debunked the Fugue paper's baseless claims about Jupiter-OT's "char-interleaving" problem. Additionally, I questioned the relevance and value of discussing concepts like "multi-user-backward-relay-interleaving," urging to direct collective efforts towards addressing genuine co-editing challenges for the advancement of the field.
In this third post, I focus on debunking the unfounded assertions made in the Fugue paper regarding the GOT algorithm. Since GOT supports string-wise co-editing, like Jupiter-OT, and can be combined with various transformation functions, it is straightforward to refute the alleged "char-interleaving" problem in GOT using the same reasoning and illustrations from my second post on Jupiter-OT. Therefore, this post aims to address broader issues, dispel misconceptions, and unveil the truth about the GOT algorithm and OT as a whole.
1.Basic Facts and Features of the GOT algorithm
The GOT (Generic Operation Transformation) work was mainly motivated to solve the classic dOPT puzzle. The GOT algorithm was initially designed and published in [1], without reference to any concrete transformation functions. Later, the combination of the GOT algorithm with a set of independently designed string-wise transformation functions was published in [2].
The GOT algorithm possesses the following main features:
a. Functioning as a distributed OT control algorithm, without relying on a central transformation server.
b.Introducing the notion of operation context and context-based transformation conditions for OT correctness.
c.Solving the dOPT puzzle by ensuring the context-equivalence condition.
d.Achieving convergence without requiring the supporting transformation functions to meet CP1 and CP2 transformation properties.
e.Incorporating a state-vector-based garbage collection scheme to remove operations from the history buffer that are no longer necessary for future transformation.
Similar to Jupiter-OT and the adOPTed algorithm, the GOT algorithm satisfies the mandatory context-based conditions required for all OT control algorithms (see Q&A 3.15-3.18 in OTFAQ [4]); and it can be combined with any suitable transformation functions (not limited to those published in [2]) to create a complete OT solution.
Differing from Jupiter-OT and the adOPTed algorithm, the GOT algorithm employs a pair of Inclusion and Exclusion transformation functions, which are obligated to meet a reversibility transformation property. This reversibility requirement increases the complexity of transformation functions and has been eliminated in subsequent OT control algorithms such as NICE, TIBOT, COT, and POT, which exclusively utilize Inclusion transformation functions.
One side-product of the GOT work is the identification of the False-Tie (FT) puzzle in text co-editing, which has influenced subsequent development in OT and the first CRDT (WOOT) in co-editing. The FT puzzle and CP2-voilation issue have been solved in numerous ways under the OT framework. Readers interested in learning more about FT and its solutions can refer to the following Q&A entries in the OTFAQ [4]:
•3.24. What is the False-Tie (FT) puzzle?
•3.25. Under what circumstances is an FT-solution needed or not needed?
•3.26. How to achieve consistency without solving the FT puzzle?
2. Text-Interleaving is Prohibited in String-Wise Transformation Functions
In the Fugue paper, it was claimed that the "interleaving" problem "has gone unnoticed for decades." However, as I highlighted in my first post, the issue of char-interleaving in some CRDT algorithms (e.g., Logoot) had already been reported as early as 2018. Furthermore, it is important to note that the matter of avoiding concurrent insertion interleaving had been explicitly addressed back in 1998 when designing string-wise transformation functions.
Section 9.1.3 "Criteria for Verifying Intention-Preserved Effects" of [2] (pp. 85-86) provides a precise specification for achieving intention-preserved effects during concurrent string-wise insert and delete operations. This specification served as a guiding principle for the design of string-wise transformation functions, which aim to achieve desired combined effects while explicitly preventing the "interleaving" of concurrent insertions. The following excerpt from [2] highlights this point:
"When the above criteria are satisfied, the execution effects of independent Insert/Delete operations will not interfere with each other in the following sense: an Insert operation may never insert a string into the middle of another string inserted by an independent operation, and a Delete operation may never delete characters inserted by independent operations."
3.Text-Interleaving is Irrelevant to OT Control Algorithms
Text-interleaving is a special concern in text co-editing. It is a common misconception in some co-editing articles to attribute text co-editing issues to generic OT control algorithms.
In the Fugue paper, Jupiter-OT, adOPTed, and GOT are implicated as the cause of text-interleaving problems. However, even if those illustrations used to support such assertions were valid (which, as demonstrated in my previous posts, they are not), assigning the responsibility of text-editing specific issues to OT control algorithms is misguided and highly misleading. The correctness of an OT control algorithm is determined by its adherence to essential context-based transformation conditions. These conditions are entirely unrelated to text-editing and, consequently, text-interleaving.
This further underscores the need for a better understanding of the principles that govern OT control algorithms and their evaluation criteria. Readers interested in learning more about OT correctness can refer to the following Q&A entries in the OTFAQ [4]:
•3.15. What are the OT algorithm correctness requirements?
•3.16. Which OT components are responsible for meeting specific algorithm correctness requirements?
•3.18. Under what conditions is an OT system algorithmically correct?
4.How to Create Correct OT Solutions by Combining Existing Control Algorithms and Transformation Functions?
A well-established approach to constructing a comprehensive OT solution involves the separation of high-level OT control algorithms from low-level transformation functions, with the specification of their interrelationships through transformation properties and conditions.
One significant advantage of this modular OT system structure is the ability to design and validate control algorithms and transformation functions independently, enabling their flexible combination to create new OT solutions tailored to specific applications, as long as they adhere to the required transformation conditions and properties. The separation and flexible combination of control algorithms and transformation functions have greatly contributed to the continuous advancement of OT and its diverse real-world applications.
Last decade has witnessed significant expansion of OT into new co-editing domains through the invention of novel transformation functions for various data types, such as QuillJS OT functions for rich-text co-editing (https://github.com/ottypes/rich-text), JSON OT functions (https://github.com/ottypes/json0), just to mention a few. Many of these novel transformation functions have been developed by open-source contributors and industry practitioners.
On the other hand, numerous OT control algorithms have been designed and most of them are invented by academic researchers [4]. Some control algorithms, like Jupiter-OT, NICE and Google OT, are Sever-based OT (SOT) algorithms that rely on a central transformation server. However, most other OT control algorithms, including adOPTed, GOT, GOTO, COT, SOCT, TIBOT, and POT, are Distributed OT (DOT) algorithms that do not require a transformation server and allow co-editing clients to connect with each other in flexible communication topologies.
With the availability of a range of OT control algorithms and open-source transformation functions, there are ample opportunities to create comprehensive OT solutions for specific applications by flexibly combining suitable control algorithms and transformation functions.
However, there is a prevalent misconception within co-editing communities that OT necessitates a central server to function. This widespread illusion can be attributed to a combination of factors, including the fact that the popular OT-based Google Docs utilizes a transformation server, a general lack of awareness and understanding of distributed OT algorithms, and the spread of misinformation. Even among experienced industrial engineers and open-source practitioners who have developed practical OT-based co-editing products or designed advanced transformation functions, there was a lack of awareness or limited knowledge about the fact that OT can function perfectly without relying on a central server. This lack of awareness and understanding, combined with the prevailing misconception, led them to mistakenly perceive that their OT systems or functions were confined to operating with a central transformation server like Google Docs.
In fact, OT control algorithms (whether SOT or DOT) and transformation functions (for any data types and applications) are independent components. The publicly available transformation functions developed by practitioners have been commonly integrated with different OT control algorithms (SOT or DOT) in various practical co-editing applications. It is worth noting that most co-editing systems adopt a client-server architecture for valid reasons [3]. If necessary, a server-based OT co-editing system can be transformed into a server-less OT-based co-editing system by adopting a distributed OT control algorithm. This conversion does not require modifying the existing transformation functions for the target application, nor does it necessitate the creation of a new OT control algorithm, as there are numerous existing options readily available.
The notion that OT is unsuitable for peer-to-peer co-editing is a false proposition. For further discussion, refer to Section 4 "Myths and Facts about Peer-to-Peer Co-Editing" in [3].
5. How to Avoid Creating Incorrect OT Solutions in Combining Control Algorithms and Transformation Functions?
While the flexible combination of control algorithms and transformation has been instrumental in creating innovative and effective OT solutions, it is important to acknowledge that this power can, and unfortunately has been, misused to generate incorrect solutions, often employed to substantiate unfounded criticisms of OT. Such misuse may arise from a limited knowledge of OT fundamentals, but its repercussions are far-reaching. It perpetuates distorted views of OT, compromises the integrity of the field, and hinders the overall progress of co-editing.
One example of such misuse can be found in the Fugue paper, which I discussed in detail in my first post of this series. The paper attempted to demonstrate the presence of char-interleaving in the adOPTed algorithm by combining it with the Tombstone Transformation Function (TTF). Unfortunately, the adOPTed algorithm was inaccurately portrayed to function similarly to the flawed dOPT algorithm. This combination of TTF with a dOPT-like algorithm resulted in an erroneous solution that generated inconsistent and interleaving outcomes. These outcomes were then used to support the assertion of an interleaving issue in the adOPTed algorithm and TTF.
In fact, TTF has no connection to char-interleaving either. However, other misconceptions surrounding TTF do exist. In some articles and talks, TTF was portrayed as a correct OT solution, while simultaneously labelling OT control algorithms (such as adOPTed) as incorrect in comparison. However, this comparison is fundamentally flawed because TTF merely comprises a set of transformation functions that must be combined with a suitable OT control algorithm to form a complete solution. Even then, TTF alone does not ensure the correctness of the resulting solution. The Fugue paper serves as a prime example of this, where the combination of TTF with a dOPT-like control algorithm yielded a flawed solution.
Another noteworthy case from the Fugue paper involves the combination of the Jupiter-OT control algorithm with a fabricated char-wise transformation function. This combination was used to justify the alleged issue of char-interleaving within the original Jupiter-OT solution.
In contrast, my second post in this series presented an alternative approach by combining the Jupiter-OT control algorithm with string-wise transformation functions, resulting in consistent and non-interleaving outcomes. Additionally, I presented another new OT solution by integrating the Jupiter-OT control algorithm with a different char-wise transformation function. This solution successfully generated consistent and non-interleaving results for concurrent char-wise insertions.
The moral of the story is clear: the power of combining OT control algorithms and transformation functions in the field of co-editing is immense, but it should be used constructively and responsibly. To harness this power effectively, it is crucial to have a better and more comprehensive understanding of the fundamentals of OT. By doing so, we can avoid potential pitfalls and accelerate the development of correct, valuable, and robust co-editing solutions that drive meaningful progress in the field.
References:
[1] C. Sun, X. Jia, Y. Zhang and Y. Yang: “A Generic Operation Transformation Scheme for Consistency Maintenance in Real-time Cooperative Editing Systems,” Proc. of ACM Conf. on Supporting Group Work, pp. 425 – 434, Nov. 16 – 19, 1997.
[2] C. Sun, X. Jia, Y. Zhang, Y. Yang and D. Chen: "Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems," ACM Transactions on Computer-Human Interaction, Vol. 5, No. 1, pp.63 – 108, Mar., 1998.
[3] D. Sun, C. Sun, Agustina, W. Cai. Real differences between OT and CRDT in building co-editing systems and real-world applications. https://arxiv.org/abs/1905.01517, May 2, 2019.
[4] C. Sun, "OTFAQ: Operational Transformation Frequently Asked Questions and Answers," https://www3.ntu.edu.sg/scse/staff/czsun/projects/otfaq/
Readers are encouraged to contact the author of this post for copies of any articles referred in this series.