Unveiling Issues with “The Art of the Fugue” Paper Regarding Jupiter-OT
Let's begin by examining the original text from the paper (A.1.3., page 19) that attempts to illustrate the "interleaving" problem in JUPITER-OT:
“The Jupiter paper does not explicitly specify the transformation function for concurrent insertions, it only describes it verbally as: ‘We arbitrarily chose to put server text first if both [i.e. server and client] try to insert at the same spot.’ We show that even this informal definition implies that the algorithm exhibits forward interleaving.
Starting with an empty document, assume that client A generates ins(1, a) followed by ins(2, b), and concurrently client B generates ins(1, x). Consider the execution at the server:
1. Assume that client A’s ins(1, a) is the first operation to reach the server, so the server simply applies it, resulting in the document a.
2. Next, client B’s ins(1, x) reaches the server. Since ins(1, a) was concurrently applied by the server, we have two concurrent insertions at the same position. Per the rule for such insertions, the server’s character, that is a, is placed first, and the client’s x second. This means B’s operation is transformed to ins(2,x) and the server’s document now reads ax.
3. Finally, client A’s ins(2, b) reaches the server. Concurrently, the server has now performed ins(2, x), which is the transformed form of B’s operation. Again we have two concurrent insertions at the same position, in this case at index 2. Per the rule above we place the server’s character x first, and the client’s character b second. This means A’s operation is transformed to ins(3, b) and the server’s document now reads axb, exhibiting forward interleaving.”
1. JUPITER-OT Capable of Supporting String-Wise Co-Editing.
I would like to refer to the following quoted statement: "We arbitrarily chose to put server text first if both [i.e., server and client] try to insert at the same spot." This statement was taken out of context from the full paragraph in the JUPITER-OT paper [1] (the first paragraph on page 119) provided below:
"The Replace operation for TextEdits deletes a region of text and inserts a string to replace it. For Replace vs. Replace, the transformation produces a final state that (a) has removed all the text requested by either Replace, (b) has inserted the text requested by each, sorted by the starting points of the delete regions. We arbitrarily chose to put server text first if both try to insert at the same spot."
Moreover, it is important to emphasise that capturing continuous text regions is an integral aspect of supporting string-wise co-editing. These regions can be generated through various actions, such as continuous typing, copy-and-pasting text segments of any size, or the continuous accumulation of text resulting from arbitrary insertions and deletions during offline co-editing. It is this natural (non-artificial) creation of continuous strings during common editing actions that underscores the undesirability of text-interleaving and justifies the efforts to avoid it in co-editing.
Regrettably, this important difference between string-wise and char-wise co-editing has often been overlooked or ignored in numerous co-editing papers that exclusively focus on char-wise text editing. This oversight is evident in the Fugue paper, where the sequential insertion of two characters "a" and "b" (by client A) was represented as two separate char-wise operations: insert(1, a) and insert(2, b), rather than a single string-wise insert(1, ab), which could have occurred with JUPITER-OT or other OT solutions capable of supporting string-wise co-editing.
With the string-wise operation "ins(1, ab)" capturing the continuous insertion of the characters "a" and "b", it is unequivocal that the final execution result at the JUPITER server should completely eliminate any possibility of interleaving, as illustrated below (with all other conditions being the same as what described in the Fugue paper):
Starting with an empty document, assume that client A initiates the insertion of two characters, “a” and “b”, sequentially, resulting in the operation "ins(1, ab)"; and concurrently client B inserts a single character “x”, leading to the operation "ins(1, x)". Now examine the execution at the server:
1. Assume that client A's ins(1, ab) is the first operation to reach the server, so the server simply applies it, resulting in the document "ab".
2. Next, client B's ins(1, x) reaches the server. Since ins(1, ab) was concurrently applied by the server, we have two concurrent insertions at the same position. According to the rule for such insertions, the server's text, "ab" is placed first, and the client's "x" is placed second. This means B's operation is transformed into ins(3, x), and the server's document now reads "abx" - a non-interleaving outcome.
If the tie-breaking rule is reversed, meaning that the server's text is placed after the client’s text when both attempt to insert at the same position, the resulting outcome would be "xab," which remains non-interleaving.
2. JUPITER-OT Restricted to Supporting Char-Wise Co-Editing
What would be the outcome if JUPITER-OT were restricted to supporting char-wise co-editing only? The straightforward answer is that consistent and non-interleaving results can still be achieved.
To demonstrate this, let's explore the combination of the JUPITER-OT control algorithm with a char-wise transformation function described in [2]. This combination is perfectly appropriate and presents no issues. The JUPITER-OT control algorithm, along with other notable OT control algorithms such as adOPTed, GOT, GOTO, COT, POT, and more, was designed to be generic. This design allows for flexible integration with different transformation functions, as elaborated in Q&A 3.19 of the OTFAQ [4] titled "How to create a correct OT system by combining existing control algorithms and transformation functions?"
In [2], when two concurrent edits insert at the same position, the tie-breaking rule states: "If the positions are equal, the operation whose request has a larger user id is shifted to the right". Under similar conditions as described in the Fugue paper (assuming A < B), the following sequence of events would unfold at the JUPITER server:
1. Assuming that ins(1, a, A) is the first operation to reach the server, it is straightforwardly applied, resulting in the document state: "a".
2. Next, ins(1, x, B) reaches the server. Since ins(1, x, B) is concurrent and context-equivalent to ins(1, a, A), the server applies the transformation T(ins(1, x, B), ins(1, a, A)), resulting in ins(2, x, B) due to the conditions 1 = 1 and A < B. Executing ins(2, x, B) yields the document state: "ax".
3. Finally, ins(2, b, A) arrives at the server. This operation is concurrent and context-equivalent to ins(2, b, B). The server applies the transformation T(ins(2, b, A), ins(2, X, B)), resulting in ins(2, b, A) due to 2 = 2 and A < B. Executing ins(2, b, A) leads to the document state: "abx" (non-interleaving).
If the tie-breaking rule is reversed (A > B), another non-interleaving result would be obtained: "xab".
Astute readers will observe the striking resemblance between the char-wise co-editing example presented above in the context of JUPITER-OT and the corrected illustration of client B using the adOPTed control algorithm in my previous post (https://news.ycombinator.com/item?id=36208787). It is clear that both the adOPTed and JUPITER-OT control algorithms consistently produce non-interleaving outcomes. This similarity is not a coincidence but rather a characteristic shared by generic OT control algorithms [3,4].
In summary, JUPITER-OT is able to consistently deliver non-interleaving outcomes, regardless of whether it is integrated with string-wise or char-wise transformation functions.
3. Moving Forward from Current State-of-the-Art of Co-Editing
Over the past three decades, co-editing has undergone significant advancements, pushing the frontiers and reshaping the landscape of co-editing in both theory and practice. Particularly noteworthy is the field has evolved long ago from early plain-text char-wise co-editing to the era of widespread adoption of string-wise co-editing and rich-text collaboration. These advancements have been integrated into real-world co-editing products, empowering users to collaboratively edit not only plain texts but also complex data structures such as stylized texts, tables, itemization, and graphics. As the field progresses to meet the growing demand for more sophisticated features and applications, new and genuine technical challenges continuously emerge, requiring us to appropriately direct our efforts towards addressing these challenges and moving the field forward.
Given the current state-of-art of co-editing and emerging challenges ahead of us, it is puzzling to witness a regressive resurgence of discussions centred around plain-text char-wise co-editing. These discussions often delve into seemingly contrived topics, one of which is "backward interleaving".
The notion of "backward interleaving" explores the possibility of char-wise interleaving under reverse order typing. For instance, by examining the scenario where a string "abc" is created in reverse order, with 'c' first, 'b' second, and 'a' last. Now, suppose another user concurrently inserts the character "x" at the same position as "a." Will "x" be injected in the middle of this backward-created string "abc" in the final merged result? That’s the question investigated under “backward interleaving”.
Similarly, discussions revolving around "multi-user-relay interleaving”, also known as "multi-replica interleaving” in the Fugue paper, where multiple users sequentially contribute characters to form a string, appear to be far-fetched. For instance, consider an imaginary scenario where user A types the character “a”, followed by user B typing “b” to form the sequence “ab”, and finally, user C adds the character “c” to complete the string as “abc”. Now, the question arises in the context of "multi-user-relay" interleaving: is there a possibility that this string “abc” becomes interleaved with another character "x" concurrently inserted by yet another user?
Further discussions regarding the combination of "multi-user-relay interleaving" and "backward interleaving" become increasingly implausible. This is demonstrated by examining the possibility of text-interleaving under a hypothetical scenario: user C initiates the process by inputting "c" and relaying it to user B, who prefixes "b" to create the sub-string "bc" before passing it on to user A. Subsequently, user A contributes the character "a," resulting in the formation of "abc." Meanwhile, user D, who is unaware of the existence of "abc," independently types the character "x" at the same position as "a.” This raises the question: Can character “x” become entwined in the middle of the string “abc”, created in such a "multi-user-backward-relay" fashion?
These scenarios starkly contrast with common string-creation activities, such as natural (forward) typing, copy-and-pasting, and text accumulation processes during offline editing, which originally prompted the investigation of text-interleaving issues in co-editing. It is legitimate to question the value of these discussions, both in theory and practice. How do they genuinely contribute to advancing the state-of-the-art of co-editing? What practical benefits do they offer?
It is crucial to critically evaluate the relevance and significance of study topics in the current and broader context of co-editing. This evaluation plays a vital role in promoting valuable research and useful applications, and propelling the co-editing field forward.
References:
[1]. D. Nichols, P. Curtis, M. Dixon, and J. Lamping: "High-latency, low-bandwidth windowing in the Jupiter collaboration system," Proc. of the ACM Symposium on User Interface Software and Technology, pp.111 – 120, Nov. 1995.
[2]. M. Ressel, D.N. Ruhland, and R. Gunzenhauser: "An integrating, transformation-oriented approach to concurrency control and undo in group editors," Proc. of the ACM Conf. on Computer Supported Cooperative Work, pp. 288 – 297, Nov. 1996.
[3] C. Sun and C.A. Ellis: “Operational Transformation in Real-Time Group Editors: Issues, Algorithms, and Achievements,” Proc. of ACM Conf. on Computer Supported Cooperative Work, pp. 59 – 68, Nov. 14 – 18, 1998.
[4]. C. Sun, "OTFAQ: Operational Transformation Frequently Asked Questions and Answers," https://www3.ntu.edu.sg/scse/staff/czsun/projects/otfaq/