There is a new CRDT algorithm for text co-editing. Are anybody interested in this CRDT algorithm and the interleaving issues brought by CRDT algorithms.
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...
The authors gave an example showing WOOT also could cause the interleaving phenomenon.
WOOT was the first CRDT algorithm for text co-editing, but the authors showed that the first CRDT algorithm has a serious flaw after the algorithm was invented 17 years ago
3 comments
[ 2.9 ms ] story [ 16.7 ms ] threadA 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:
WOOT was the first CRDT algorithm for text co-editing, but the authors showed that the first CRDT algorithm has a serious flaw after the algorithm was invented 17 years ago