shunza

A Critical Examination of "The Art of the Fugue" Paper in Relation to OT The introductory paragraph of the paper's abstract states:

"Existing algorithms for replicated lists, which are widely used in collaborative text editors, suffer from a problem: when two users concurrently insert text at the same position in the document, the merged outcome may interleave the inserted text passages, resulting in corrupted and potentially unreadable text. The problem has gone unnoticed for decades, and it affects both CRDTs and Operational Transformation."

The issue of text interleaving in certain CRDT solutions, such as Logoot, is not a recent or overlooked problem. In fact, it has been independently reported by several researchers and practitioners as early as 2018. For detailed visual representations, please refer to Figure 2 and Section 4.4 in [1]. An earlier version of this paper was also published in 2018 and can be accessed at https://arxiv.org/abs/1810.02137.

What sets "The Art of the Fugue" paper apart is its identification of the interleaving problem in several early OT solutions, namely JUPITER OT [1994], adOPTed control algorithm [1996], GOT control algorithm [1998], and TTF functions [2006]. However, even if we were to accept the reported interleaving problem in these co-editing solutions as valid (which is not the case, as later shown), it would be highly unjustifiable to make sweeping claims such as "existing algorithms for replicated lists, which are widely used in collaborative text editors,” suffer from the interleaving problem, or "all text collaboration algorithms have an interleaving problem” (claimed elsewhere by a co-author). This is due to the existence of numerous other co-editing solutions not covered in the paper, including GOTO (ACM CSCW1998), NICE (ACM CSCW2002), TIBOT (IEEE ICPADS2004), COT (ACM CSCW2006), GOOLGO WAVE and Docs OT (2010), and POT (IEEE TPDS2016), to name just a subset of the vast co-editing landscape. It is important to acknowledge that these examples do not encompass a considerable number of industry and open-source OT solutions as well.

Having been involved in co-editing since the 1990s, I have extensive familiarity with various OT solutions, including those mentioned in "The Art of the Fugue" paper (refer to [2]). However, I must admit that I was previously unaware of the interleaving problem in any of these solutions. Naturally, the report in "The Art of the Fugue" paper has sparked my curiosity, prompting me to review these early works to identify any overlooked aspects and evaluate the validity of "The Art of the Fugue" paper's claims.

Regrettably, after thorough review, I find the claims in the paper regarding these co-editing solutions to be unfounded. To share my findings with fellow researchers and practitioners, I will publish a series of reviews on HN. These reviews will address each solution in relation to "The Art of the Fugue" paper, aiming to contribute to knowledge advancement in co-editing and provide accurate information to those who depend on it.

What’s wrong with “The art of the Fugue” paper about OT (adOPTed)?

Let's examine the original text from the paper (A.1.1. page 18) that attempts to illustrate the "interleaving" problem in the adOPTed algorithm:

   “To demonstrate forward interleaving, replica A generates ins(1, a, A) followed by ins(2, b, A). Concurrently, replica B generates ins(1, x, B). Assume A < B and consider the execution at B:

   1. B executes ins(1, x, B), so the document is x.

   2. When B receives ins(1, a, A), it computes the transformation T(ins(1,a,A),ins(1,x,B))=ins(1,a,A) because 1=1 & A<B so a is inserted before x, yielding ax.

   3. When B receives ins(2, b, A), it computes the transformation T (ins(2, b, A), ins(1, x, B)) = ins(3, b, A) because 2 > 1, so b is inserted after x, yielding axb.”

Additionally, it is worth noting that the adOPTed control algorithm should produce ins(2, x, B) in Step 2 using the transformation T(ins(1, x, B), ins(1, a, A)) because 1=1 & A<B. This important aspect was missing in "The Art of the Fugue" paper.

To gain a deeper understanding of the underlying issues involved, let's further explore an illustration of what would occur at replica A (not depicted in "The Art of the Fugue" paper) under the same scenario:

     1. Replica A sequentially executes ins(1, a, A) and ins(2, b, A), resulting in the document being ab.

     2. When A receives ins(1, x, B), it computes two transformations in sequence: a. T(ins(1, x, B), ins(1, a, A)) = ins(2, x, B) because 1=1 & A<B. b. T(ins(2, x, B), ins(2, b, A)) = ins(3, x, B) because 2=2 & A<B.

   As a result, x is inserted after ab, yielding abx at replica A.

    (ins(1, a, A) -> ins(2, b, A)) || ins(1, x, B)

Therefore, it is important to highlight that the key aspect of solving the dOPT-puzzle, achieved by OT control algorithms like adOPTed, JUPITER, GOT, GOTO, COT, POT, and GOOGLE OT, is to ensure context-equivalence between the two input operations processed by the transformation function. Context-equivalence, as further explained in OTFAQ [2], means that the operations are defined on the same state. In the provided example, ins(2, b, A) is context-equivalent to ins(2, x, B), whereas it is context-inequivalent to ins(1, x, B). Emphasising this principle is crucial for a comprehensive understanding of OT and to avoid misconceptions in its application.

Lastly, I want to address why I excluded TTF from the previous discussions. The reason is that TTF does not bear relevance to illustrating the "interleaving" issue or resolving the dOPT-puzzle. When TTF is not integrated with a suitably correct OT control algorithm like adOPTed but instead combined with a flawed one like dOPT (as portrayed in "The Art of the Fugue" paper), inconsistencies inevitably arise. This is evident when we combine the illustration at replica B in the paper with the additional illustration at replica A, demonstrating the effect of integrating TTF with a dOPT-like algorithm.

In conclusion, it is vital to grasp the resolution to the dOPT-puzzle and recognise the significance of ensuring context-equivalence in OT control algorithms like adOPTed, JUPITER, GOT, GOTO, COT, POT, and GOOGLE OT, among others. This understanding is crucial in dispelling misconceptions and flawed arguments surrounding OT and preventing the repetition of similar mistakes in the future.

[1] David Sun, Chengzheng Sun, Agustina Ng, and Weiwei Cai. Real differences between OT and CRDT in correctness and complexity for consistency maintenance in co-editors. Proceedings of the ACM on Human-Computer Interaction, 4(CSCW1), May 2020. doi:10.1145/3392825. Also available at https://arxiv.org/abs/1905.01302, May 2, 2019.

[2]. Chengzheng Sun, “OTFAQ: Operational Transformation Frequently Asked Questions and Answers,” https://www3.ntu.edu.sg/scse/staff/czsun/projects/otfaq/

First, in Logoot (https://hal.inria.fr/inria-00432368/document", the function generateLinePositions in section 4.2 has a serious error, which could lead to the failure of generating new identifiers. This flawed design can be also found in the following research (Logoot-Undo, https://hal.inria.fr/hal-00450416/)

Second, in TreeDoc (https://hal.inria.fr/inria-00445975/document), the function newPosID described in section 3.2 may generate incorrect ids. This function is to generate an id r between any two ids p and q (p<q) so that p<r<q. However, in line 5, if pn=0, then we would get r<p. Readers can refer to Figure 3, in the tree, the character dY precedes the character dZ in infix order, however, the id of dY (10(0:dY)) is greater than the id of dZ (100(1:dZ)), thus their positions are inconsistent their ids.

In the literature, CRDT researchers always claim their CRDT designs are formally proved.

However, there are various scenarios whereby CRDTs would have inconsistency issues as stated above.

In my opinion, I don't think there are much validity for these claims.

[1] https://dl.acm.org/citation.cfm?id=2914099