<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Stories by Dr. Chengzheng Sun on Medium]]></title>
        <description><![CDATA[Stories by Dr. Chengzheng Sun on Medium]]></description>
        <link>https://medium.com/@czsun08?source=rss-e237dc30292a------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*82Pvaa7E_XiYTo2Kh-c7nA.png</url>
            <title>Stories by Dr. Chengzheng Sun on Medium</title>
            <link>https://medium.com/@czsun08?source=rss-e237dc30292a------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Mon, 16 Nov 2026 13:49:09 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@czsun08/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Op-Set Convergence ⇒ Quiescent Convergence]]></title>
            <link>https://medium.com/@czsun08/op-set-convergence-quiescent-convergence-134b5ea009cc?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/134b5ea009cc</guid>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Fri, 13 Feb 2026 02:58:36 GMT</pubDate>
            <atom:updated>2026-02-16T11:30:08.492Z</atom:updated>
            <content:encoded><![CDATA[<h4>Demystifying “Eventual Consistency” in Co-Editing CRDTs</h4><p>After <a href="https://medium.com/@czsun08/convergence-intention-preservation-ed3f3095bcc0">Post 1</a>, we can say something very crisply:</p><blockquote><strong><em>Convergence is not the same thing as Intention-Preservation.</em></strong></blockquote><p>Now we can focus on convergence itself — and fix one of the biggest terminology traps in co-editing: the way “<em>convergence</em>”, “<em>eventual </em>consistency”, “<em>eventual convergenc</em>e” get mixed together.</p><p>OT literature [2] and OTFAQ [3] define convergence as an <strong>operation</strong>-<strong>set-based invariant</strong>: replicas match when they’ve incorporated the same operations. I’ll call that:</p><blockquote><strong><em>Op-Set Convergence</em></strong></blockquote><p>Then, assuming the delivery/liveness guarantees that modern co-editors (OT or CRDT) typically rely on, Op-Set Convergence implies a weaker end-state property:</p><blockquote><strong><em>Quiescent Convergence</em></strong></blockquote><p>This post shows how that chain:</p><blockquote><strong><em>Op-Set Convergence ⇒ Quiescent Convergence</em></strong></blockquote><p>makes co-editing CRDT “<em>eventual consistency</em>” much less mysterious — and why OT’s set-based convergence is more practically actionable (especially for debugging and engineering).</p><h3>What OT really means by “convergence”</h3><p>OT literature does <strong>not</strong> define convergence as:</p><ul><li>“everyone matches after each operation”</li><li>“replicas are always equal”</li><li>“same number of steps”</li></ul><p>Instead, OT literature (e.g. TOCHI’98 paper [2] and OTFAQ [3]) defines convergence as a <strong>set-based guarantee </strong>:</p><blockquote><strong><em>“Convergence requires the copies of the shared document be identical when the same group of operations has been performed, particularly at the end of a collaboration session”</em></strong> in <em>[3] (QA 3.2)</em>.</blockquote><p>That’s a <em>set-based invariant</em>, not a time-based promise. So, a better name: <strong>Operation Set (Op-Set) Convergence.</strong></p><blockquote><strong><em>Same executed operation set ⇒ same document state.</em></strong></blockquote><p>This matches how real co-editors behave:</p><ul><li>local operations execute immediately (responsiveness)</li><li>delivery orders may differ</li><li>temporary divergence is normal</li><li>but <strong>op-set equality implies state equality</strong></li></ul><blockquote><strong><em>This is not a bug. It’s the design.</em></strong></blockquote><h3>Quiescent Convergence is just the end result</h3><p>If the system guarantees liveness (updates are eventually delivered — a standard assumption in modern co-editors), then eventually:</p><ul><li>all replicas end up with the same op-set</li><li>therefore, by op-set convergence, all replicas end up with the same state</li></ul><p>That yields a weaker derived notion: <strong>Quiescent Convergence</strong></p><blockquote><em>When updates stop and delivery completes, replicas converge.</em></blockquote><p><strong>Op-set convergence is the engine.</strong><br><strong>Quiescent convergence is just the destination.</strong></p><h4>A brief historical note: the evolution of “convergence” in OT</h4><blockquote>The earliest OT work (<strong><em>dOPT</em></strong><em> in [1])</em> defined convergence in a quiescent form: replicas were required to match once all operations had been delivered and no further updates were pending.</blockquote><blockquote>Beginning with the <strong>TOCHI’98</strong> paper <em>[2]</em>, convergence was reformulated. Convergence was distinguished from <strong>Intention-Preservation</strong>, and defined as a stronger invariant: replicas that have executed the same group (set) of operations must be in identical states.</blockquote><blockquote>This shift marks the transition from a purely quiescent notion of convergence to what we now call <strong>Op-Set convergence</strong>, explicitly combined with <strong>Intention-Preservation</strong> as a separate requirement.</blockquote><h3>An Op-Set Convergence example</h3><p>This example is adapted from <strong>Section 10 (“An Integrated Example”)</strong> in TOCHI’98 [2]. We intentionally abstract away:</p><ul><li>concrete document strings,</li><li>operation parameters,</li><li>transformed forms and internal undo/redo details.</li></ul><p>Those details are important for showing <strong>Intention-Preservation</strong> and combined effects, and the paper is the authoritative source for them. Here we focus only on <strong>when and where operations are generated and executed</strong>, to highlight Op-Set Convergence.</p><h4>Operation generation, execution order, and stages</h4><p>There are three replicas: <strong>R0, R1, R2</strong>.<br> Four operations are generated as follows:</p><ol><li><strong>O1</strong> generated at <strong>R0</strong></li><li><strong>O2</strong> generated at <strong>R1</strong></li><li><strong>O3</strong> generated at <strong>R1</strong>, after executing local <strong>O2</strong> and remote <strong>O1</strong></li><li><strong>O4</strong> generated at <strong>R2</strong>, after executing remote <strong>O2</strong></li></ol><p>Due to network latency, operation execution orders differ:</p><ul><li><strong>R0 execution order:</strong> O1, O2, O4, O3</li><li><strong>R1 execution order:</strong> O2, O1, O3, O4</li><li><strong>R2 execution order:</strong> O2, O4, O1, O3</li></ul><h4>How to read the stages</h4><ul><li>A replica reaches <strong>Stage j</strong> after it has executed its <strong>j-th operation</strong> (local or remote).</li><li><strong>Stage numbers are local execution counts</strong>, not “global steps.”</li><li>Stage boundaries are <strong>independently determinable by each replica</strong>.</li><li>Two replicas can be at the same stage while having executed <strong>different operations</strong>.</li></ul><h4>Op-sets at each stage (Stage 0–4)</h4><h4>Notation</h4><ul><li><strong>DSⁱⱼ</strong> = document state at replica/site <strong>i</strong> after <strong>stage j</strong></li><li><strong>OpSetⁱⱼ</strong> = set of operations executed at replica/site <strong>i</strong> after <strong>stage j</strong></li></ul><p>Where:</p><ul><li><strong>i ∈ {0,1,2}</strong> (replica/site)</li><li><strong>j ∈ {0,1,2,3,4}</strong> (stage / number of executed ops so far)</li></ul><h4>OpSet table</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*p-ErZTdmLIoKEFYH1Unnzg.png" /></figure><h4>Deriving convergence directly from op-set equality</h4><p>Apply the Op-Set Convergence invariant:</p><blockquote><strong>If OpSetⁱⱼ = OpSetᵏⱼ, then DSⁱⱼ = DSᵏⱼ, for any i, k ∈ {0, 1, 2} with i≠k</strong>.</blockquote><h4>Stage 0 (init state)</h4><p>OpSet⁰₀ = OpSet¹₀ = OpSet²₀<br> ⇒ <strong>DS⁰₀ = DS¹₀ = DS²₀</strong></p><h4>Stage 1 (Partial Op-Set Convergence and Legitimate Divergence)</h4><p>OpSet⁰₁ ≠ OpSet¹₁ = OpSet²₁<br> ⇒ <strong>DS⁰₁ ≠ DS¹₁ = DS²₁</strong></p><h4>Stage 2 (Partial Op-Set Convergence and Legitimate Divergence)</h4><p>OpSet⁰₂ = OpSet¹₂ ≠ OpSet²₂<br> ⇒ <strong>DS⁰₂ = DS¹₂ ≠ DS²₂</strong></p><h4>Stage 3 (Partial Op-Set Convergence and Legitimate Divergence)</h4><p>OpSet⁰₃ = OpSet²₃ ≠ OpSet¹₃<br> ⇒ <strong>DS⁰₃ = DS²₃ ≠ DS¹₃</strong></p><blockquote><strong><em>Note on Stage 3 in TOCHI’98 [2].</em></strong><em><br></em>In the published paper, Stage 3 is reported as <em>DS⁰₃ = DS¹₃ ≠ DS²₃</em>. Based on the execution ordering in the integrated example and the corresponding operation-set analysis, this appears to involve a typographical swapping of <em>DS¹₃</em> and <em>DS²₃</em>, i.e., the relation should read <em>DS⁰₃ = DS²₃ ≠ DS¹₃</em>. This does not affect the underlying Op-Set–based reasoning.</blockquote><h4>Stage 4 (quiescence convergence)</h4><p>OpSet⁰₄ = OpSet¹₄ = OpSet²₄<br> ⇒ <strong>DS⁰₄ = DS¹₄ = DS²₄</strong></p><h4>One important message:</h4><blockquote><strong><em>Under Op-Set Convergence, replicas may converge, diverge, and re-converge multiple times before quiescence.</em></strong></blockquote><p>This is why Op-Set Convergence is a <strong>safety invariant you can check during execution</strong>, not just a property of the final state.</p><p>For full details about document strings, operation parameters, transformed forms, and how <strong>Intention-Preservation</strong> and combined effects are ensured throughout the execution — see TOCHI’98 Section 10 [2].</p><h3>Where CRDT “eventual consistency” fits</h3><p>In co-editing CRDT papers, although various formulations exist, “eventual consistency” is commonly expressed in the classic quiescence form:</p><blockquote>Eventual consistency … guarantees that <strong>if no new update is made to the object, eventually all accesses will return the same value <em>[5]</em>.</strong></blockquote><p>Under the same liveness assumption used by modern co-editing systems, this reduces to:</p><blockquote><strong><em>Quiescent Convergence.</em></strong></blockquote><p>Nothing magical — just the fixed point once everyone has seen everything.</p><p>Importantly, “eventual consistency” by itself does <strong>not</strong> include <strong>Intention-Preservation</strong> as defined and required in OT. It guarantees convergence of state, but says nothing about whether each operation achieves the effect it was originally intended to have.</p><h3>Why Op-Set Convergence is powerful</h3><p>Op-set convergence isn’t just a correctness statement.</p><p>It’s an <strong>engineering tool.</strong></p><h4>1) Safe temporary divergence</h4><p>Replicas may diverge freely as long as their op-sets differ.<br>Local operations can execute immediately (responsiveness). No locks. No barriers.</p><h4>2) History reshaping, merge, GC</h4><p>Because state depends on what operations happened, not how they were ordered/executed:</p><ul><li>redundant operations can be merged or canceled into equivalent operations</li><li>old operations can be garbage-collected aggressively</li><li>operations can be undone/redone internally</li></ul><h4>3) Early inconsistency detection (debugging superpower)</h4><p>Op-set convergence gives you a simple runtime assertion:</p><blockquote><strong><em>Same op-set, different state ⇒ system bug.</em></strong></blockquote><p>That enables early detection of subtle concurrency errors using lightweight state signatures (size/hash), and dramatically improves debugging in distributed sessions.</p><p>Quiescent convergence alone can’t do this — because you don’t know whether a mismatch is a bug or just “not all updates delivered yet.”</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*d6ug3QrCpOspgZHE5VS1WA.png" /><figcaption><strong>Figure 1.</strong> Op-Set Convergence enables early detection of inconsistency bugs: if replicas share the same operation set but differ in state signatures, consistency maintenance has failed.</figcaption></figure><h3>Why early divergence detection matters so much</h3><p>Debugging a distributed, concurrent, real-time co-editing system is notoriously hard — not “hard in theory,” hard in day-to-day engineering.</p><p>Here’s why.</p><h4>1) Most co-editing bugs don’t crash — they silently corrupt state</h4><p>In a co-editor:</p><ul><li>operations arrive in different orders</li><li>replicas legitimately diverge temporarily</li><li>the UI keeps responding</li><li>everything <em>looks</em> fine</li></ul><p>A subtle bug in consistency maintenance rarely causes:</p><ul><li>a crash</li><li>an exception</li><li>an obvious error message</li></ul><p>Instead, it causes something worse:</p><blockquote><strong><em>A replica quietly drifts into a wrong state.</em></strong></blockquote><p>And you often don’t notice until:</p><ul><li>minutes later,</li><li>after several more operations,</li><li>or when a user reports “my document looks different from yours.”</li></ul><p>At that point, the bug is extremely hard to localize.</p><h4>2) Without Op-Set Convergence, you can’t tell “bug” from “delay”</h4><p>In systems that only rely on <strong>quiescent convergence</strong> (or “eventual consistency”).</p><p>If two replicas differ right now, you can’t tell:</p><ul><li>is this a real consistency bug?</li><li>or is it just that some updates haven’t arrived yet?</li></ul><p>So developers tend to shrug and say:</p><blockquote><em>“It’ll probably converge eventually.”</em></blockquote><p>That mindset is dangerous.</p><p>It means:</p><ul><li>real bugs can hide for a long time,</li><li>logs become huge and hard to reason about,</li><li>reproducing the problem becomes guesswork.</li></ul><h4>3) Op-Set Convergence gives you a hard invariant you can assert</h4><p>With <strong>Op-Set Convergence</strong>, you get a powerful rule:</p><blockquote><strong><em>If two replicas have the same operation set, they must have the same document state.</em></strong></blockquote><p>This immediately gives you a <strong>debugging superpower</strong>:</p><ul><li>Track each replica’s op-set (or a compact summary: vector clock, op count, IDs).</li><li>Track a cheap state signature (length, hash, checksum).</li><li>When op-sets match, states <strong>must</strong> match.</li></ul><p>If they don’t:</p><blockquote><strong><em>You have found a real bug. Right now.</em></strong></blockquote><p>No waiting. No ambiguity.</p><h4>4) This turns debugging from “post-mortem archaeology” into “early tripwires”</h4><p>In practice, this means:</p><ul><li>You can add lightweight runtime checks: <strong>same op-set + different hash ⇒ log immediately.</strong></li><li>You can catch bugs close to where they occur, before the document drifts further.</li><li>You can often: dump a small, relevant operation window, and reproduce deterministically.</li></ul><p>Instead of reconstructing a distributed history after the fact, you catch the violation <strong>at the moment the invariant breaks</strong>.</p><p>That’s a massive reduction in debugging cost.</p><h4>5) This is especially valuable under real-world concurrency patterns</h4><p>Real users don’t behave like test cases:</p><ul><li>they type quickly</li><li>they undo/redo</li><li>they reconnect</li><li>they edit on flaky networks</li><li>they collaborate in bursts</li></ul><p>These patterns are exactly where:</p><ul><li>concurrency bugs hide,</li><li>corner cases occur,</li><li>timing assumptions break.</li></ul><p>Op-Set Convergence lets you say:</p><blockquote><em>“No matter how messy the timing is, </em>this invariant must hold once the op-sets align<em>.”</em></blockquote><p>That’s a solid anchor in an otherwise chaotic system.</p><h4>6) Why this is harder (or impossible) with quiescent convergence alone</h4><p>If your only guarantee is:</p><blockquote><em>“Eventually, when everything is delivered, replicas will converge…”</em></blockquote><p>Then during development and testing:</p><ul><li>you can’t confidently assert anything <em>now</em></li><li>you can’t easily distinguish: transient divergence from real corruption</li><li>bugs tend to surface late, indirectly, and expensively</li></ul><p>You end up debugging symptoms instead of causes.</p><h4>7) The developer takeaway</h4><p>For engineers building real-time co-editors:</p><ul><li><strong>Op-Set Convergence isn’t just about correctness.</strong></li><li>It’s about <strong>observability</strong>.</li><li>It’s about <strong>fast failure</strong> instead of silent corruption.</li><li>It’s about turning a distributed system into something you can actually reason about.</li></ul><p>Or put more bluntly:</p><blockquote><strong><em>Op-Set Convergence gives you a place to stand while the system is moving underneath you.</em></strong></blockquote><p>That’s why experienced teams value it so highly — often more than abstract-sounding guarantees like “eventual consistency.”</p><h3>Why CRDTs can’t exploit the same freedom as OT</h3><p>Sequence CRDTs for co-editing (e.g., WOOT-style designs and descendants like Yjs) are <strong>content-centric</strong> [4]: they embed concurrency control into the <strong>internal content state</strong>. After integration, operations (local or remote) effectively become part of that content state (IDs, tombstones, ordering metadata/trees), so the boundary between “operation” and “content” becomes blurred and intertwined.</p><p>In that world, it’s harder to reason using <strong>op-based invariants</strong> like <strong>Op-Set Convergence</strong> or <strong>Intention-Preservation</strong>, because the system’s semantics are largely determined by how these internal content structures resolve conflicts. The natural correctness story becomes <strong>state-based</strong>: replicas converge once updates stop and all internal state has been integrated everywhere (<strong>quiescent convergence</strong>). Since concurrency is “baked into” the content state, rewriting or discarding that structure is risky — what looks like “history” is often part of the <strong>addressing and ordering substrate</strong>.</p><p>By contrast, OT is <strong>concurrency-centric</strong> by design [4]: it handles concurrency explicitly in <strong>control algorithms</strong> (based on operation concurrency/context relationships) and uses <strong>transformation functions</strong> for application-specific operation adjustments. This keeps operations as first-class objects (with timestamps/IDs) and maintains a bounded <strong>operation history</strong> (a concurrency window). That makes <strong>Op-Set Convergence</strong> and <strong>Intention-Preservation</strong> feel native and enforceable during execution — and enables practical freedoms like merging/canceling redundant operations, garbage-collecting operations outside the concurrency window, and runtime checking (“same op-set + different signature ⇒ bug”).</p><p>In summary, OT’s operation-layer concurrency model aligns naturally with <strong>op-based invariants</strong> and bounded history management, while content-centric CRDTs tend toward <strong>quiescent, state-based convergence</strong> with metadata tightly coupled to content. This isn’t just stylistic: it shapes what the system can safely optimize, what it must retain, and how confidently it can reason about correctness during execution.</p><h3>Final thought</h3><p>Here’s the whole story in one line:</p><blockquote><strong><em>Op-Set Convergence (set-based invariant) ⇒ Quiescent Convergence (end state), and co-editing CRDT “eventual consistency” is essentially the latter in modern co-editors with delivery guarantees.</em></strong></blockquote><p>So the label <strong>“eventual consistency”</strong> does not, by itself, make a design more advanced or introduce guarantees beyond convergence at quiescence.</p><p>What matters in practice is what you can do <strong>before</strong> quiescence:</p><ul><li><strong>Op-Set Convergence</strong> gives you a strong invariant you can check during execution (“same op-set, different state ⇒ bug”).</li><li>It enables aggressive GC, history rewriting, undo, and merge/cancel strategies in co-editing systems.</li></ul><p>If you’re evaluating co-editing designs, don’t let theoretical labels like <strong>“eventual consistency”</strong> distract from the real questions. Ask:</p><ul><li>What invariant is enforced during execution?</li><li>What metadata must persist?</li><li>What can the system detect early when something goes wrong?</li></ul><p>In distributed co-editing, correctness isn’t declared by labels — it’s enforced by invariants.</p><p>And Op-Set Convergence isn’t just a theoretical refinement. It is a <strong>proven engineering principle</strong>, used across decades of OT-based collaborative system research, design and implementation — from the web-based <strong>REDUCE</strong> co-editor reported in TOCHI’98 [2], to <strong>CoWord</strong>, <strong>CoPowerPoint</strong>, <strong>CoMaya</strong> [3], and later web-based collaborative products such as <a href="https://www.codox.io/"><strong>codoxApps</strong></a>.</p><h3>References</h3><p>[1] C. A. Ellis and S. J. Gibbs: “<em>Concurrency control in groupware systems</em>,” Proc. of the ACM SIGMOD Conf. on Management of data, pp. 399–407, 1989</p><p>[2] C. Sun, X. Jia, Y. Zhang, Y. Yang, D. Chen, <a href="https://dl.acm.org/doi/10.1145/274444.274447"><em>Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems</em></a><em>,</em> ACM TOCHI 1998. Pages 63–108.</p><p>[3] C. Sun, <a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/"><em>OTFAQ: Operational Transformation Frequently Asked Questions and Answers</em></a><em>.</em></p><p>[4]<a href="https://arxiv.org/abs/1905.01302"> D. Sun, C. Sun, Agustina Ng, and W. Cai: “Real differences between OT and CRDT in correctness and complexity for consistency maintenance in co-editors,” </a>PACM on Human-Computer Interaction (CSCW1), 2020</p><p>[5] S. Martin, M. Ahmed-Nacer, P. Urso, <em>Controlled conflict resolution for replicated documents</em>, <a href="https://dl.acm.org/doi/proceedings/10.5555/2916707">CollaborateCom 2012</a>. pp. 471–480.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=134b5ea009cc" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Convergence ≠ Intention-Preservation]]></title>
            <link>https://medium.com/@czsun08/convergence-intention-preservation-ed3f3095bcc0?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/ed3f3095bcc0</guid>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Fri, 13 Feb 2026 02:51:13 GMT</pubDate>
            <atom:updated>2026-02-13T03:00:40.215Z</atom:updated>
            <content:encoded><![CDATA[<h4>Clarifying Core Consistency Requirements in Co-Editing Systems</h4><p>Real-time co-editing debates often get stuck because people use “convergence” as a catch-all word for correctness.</p><p>It isn’t.</p><p>In co-editing systems, <strong>Convergence</strong> and <strong>Intention-Preservation</strong> are two different requirements. You can satisfy one and still fail the other — and a lot of confusion around OT vs CRDT starts right there.</p><p>In this post, I’ll start by defining the <strong>three core consistency requirements</strong> that appear throughout co-editing research and systems engineering (Causality-Preservation, Convergence, Intention-Preservation), then use a couple of tiny examples to show why:</p><blockquote><em>Convergence ≠ Intention-Preservation</em></blockquote><p>That distinction is the foundation for Post 2, where we’ll sharpen what OT means by <strong>convergence</strong> and connect it to what CRDT papers call “<strong>eventual consistency</strong>.”</p><h3>Three Consistency Requirements Most co-editors Care About</h3><p>Most serious co-editors aim for these [1]:</p><h4>1) Causality-Preservation</h4><p>If operation B was created <em>after</em> observing operation A, then everyone should apply <strong>A before B</strong>.</p><p>Otherwise people see replies before questions, deletions before insertions they depend on, etc.</p><h4>2) Convergence</h4><p>Once replicas have incorporated the same work, they should show the <strong>same document</strong>.</p><h4>3) Intention-Preservation</h4><p>Each operation should have the same effect as intended at creation time — despite concurrency.</p><blockquote>In this series, “intention” means <em>operation intention</em>: the effect the operation was meant to have on the document state at the moment it was created (not a human’s deeper semantic intent).</blockquote><p>Now the critical point: these are <strong>not</strong> synonyms.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*V_7QbAXszRAb-viwhrMXjA.png" /><figcaption>Figure 1. The three consistency requirements commonly discussed in co-editing systems.</figcaption></figure><h3>Two tiny examples that end the convergence-vs-intention debate</h3><p>Most arguments collapse because convergence and intention are treated as synonyms. They are not.</p><h4>Example A — Intention preserved, convergence broken</h4><p>Start with &quot;&quot;.</p><ul><li>Alice inserts &quot;a&quot; at position 0.</li><li>Bob concurrently inserts &quot;b&quot; at position 0.</li></ul><p>Both operation intentions can be preserved by either &quot;ab&quot; or &quot;ba&quot;.</p><p>But if one replica ends &quot;ab&quot; and another ends &quot;ba&quot;:</p><ul><li>✅ operation intention preserved</li><li>❌ convergence violated</li></ul><blockquote><strong><em>Operation intention does not imply convergence.</em></strong></blockquote><h4>Example B — Convergence preserved, intention broken</h4><p>Start with &quot;abc&quot;.</p><ul><li>Alice inserts &quot;X&quot; between a and b (wants &quot;aXbc&quot;).</li><li>Bob concurrently inserts &quot;Y&quot; between b and c (wants &quot;abYc&quot;).</li></ul><p>A naive “serializing everything” approach might converge to &quot;aXYbc&quot; on every site.</p><p>Replicas match — but Bob’s operation intention is violated (he expected &quot;aXbYc&quot;).</p><blockquote><strong><em>Convergence does not imply Intention-Preservation.</em></strong></blockquote><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*yKZMtlHsV3f5V5b3Im9CbQ.png" /><figcaption><strong>Figure 2.</strong> Intention-Preservation and Convergence are independent properties. A system may preserve operation intentions while diverging, or converge while violating operation intentions.</figcaption></figure><h4>Why distinctions matter</h4><p>Because <strong>convergence alone is easy</strong> (achievable by serializing everything).<br>But <strong>intention preservation is the hard part</strong> — and it’s why OT exists [2].</p><p>Classic OT literature separated these concerns deliberately. Many discussions blur these distinctions — and that’s where confusion starts.</p><h3>A Realistic Example: Why Convergence Isn’t Enough</h3><p>Let’s make the problem concrete with 0-based <em>indices</em> — because <strong>position shifting</strong> is where naive “just serializing it” falls apart.</p><p><strong>Initial document state</strong>: “The system is responsive”.</p><h4>The concurrent edits by User A and User B</h4><p><strong>User A</strong> wants to emphasize responsiveness:</p><ul><li><strong>O1 = insert[14, “highly “]</strong><br> Intended effect: “The system is <strong>highly</strong> responsive”</li></ul><p><strong>User B</strong> refines the claim in two steps:</p><ul><li><strong>O2 = insert[4, “real-time “]</strong></li><li><strong>O3 = insert[36, “ and reliable”]</strong> (after O2)</li></ul><p>So the <em>causality</em> relationship is:</p><p><strong>O2 → O3</strong>, and <strong>O1 ‖ (O2 → O3)</strong></p><p>What we <em>want</em> (intention-preserving combined effect):</p><blockquote><em>“The real-time system is highly responsive and reliable”</em></blockquote><p>That is the result commonly achieved by OT-based co-editors.</p><h4>What naive serialization (without OT) does</h4><h4>Order 1: O1 → O2 → O3</h4><p>After O1: “The system is highly responsive”.</p><p>After O2 (still insert at index 4): “The real-time system is highly responsive”.</p><p>Now O3 tries to insert at index 36 — but that index was computed for a different context (after O2, not after O1+O2). So index 36 lands <strong>inside</strong> “responsive” and splits it:</p><blockquote><em>“The real-time system is highly respo and reliablensive”</em></blockquote><p>Convergent? Yes (provided all sites serialize operations in the same order).<br> Acceptable? No.</p><h4>Order 2: O2 → O3 → O1</h4><p>After O2: “The real-time system is responsive”</p><p>After O3: “The real-time system is responsive and reliable”</p><p>Now O1 inserts at index 14 — which used to be the start of “responsive,” but isn’t anymore. It lands <strong>inside</strong> “system”:</p><blockquote><em>“The real-time shighlyystem is responsive and reliable”</em></blockquote><p>Again: convergent (provided all sites serialize operations in the same order), but nonsense.</p><h4>The punchline</h4><p>Convergence alone guarantees:</p><blockquote><em>everyone ends with the same string.</em></blockquote><p>It does <strong>not</strong> guarantee:</p><blockquote><em>each operation achieves the same effect it was intended to achieve at creation time.</em></blockquote><p>And users don’t care that all replicas match if the sentence is mangled.</p><p>That’s why <strong>Intention-Preservation</strong> is not optional in real co-editors — it’s what makes concurrent edits produce a <em>reasonable combined effect</em> instead of broken text.</p><blockquote><strong><em>Convergence ensures identical replicas.<br>Intention-Preservation achieves meaningful results.</em></strong></blockquote><h3>The key takeaway</h3><ul><li><strong>Convergence</strong> is about replica equality (under the right conditions).</li><li><strong>Intention-Preservation</strong> is about each operation achieving the same effect as intended at creation time.</li><li>These are independent: you can converge while breaking intention, or preserve intention while still diverging.</li></ul><p>Once you keep those concepts separate, the OT vs CRDT discussion becomes much clearer.</p><p><strong>Next (Post 2):</strong> we’ll refine convergence into <strong>Op-Set Convergence</strong>, show why <strong>Quiescent Convergence</strong> is just a corollary under liveness assumptions, and use that to demystify “<strong>eventual consistency</strong>” in co-editing CRDTs.</p><p>👉 <a href="https://medium.com/p/134b5ea009cc?postPublishedType=initial">That’s where we’re going next</a>.</p><h4>References</h4><p>[1] C. Sun, <a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">“<em>OTFAQ: Operational Transformation Frequently Asked Questions and Answers.</em>”</a></p><p>[2] C. Sun, X. Jia, Y. Zhang, Y. Yang, D. Chen, <a href="https://dl.acm.org/doi/10.1145/274444.274447"><em>Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems</em></a><em>,</em> ACM TOCHI 1998. Pages 63–108.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=ed3f3095bcc0" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[OT Explained for Git Users: Rebase Every Edit, Get a Merge Outcome for Free]]></title>
            <link>https://medium.com/@czsun08/ot-explained-for-git-users-rebase-every-edit-get-a-merge-outcome-for-free-0295a707cd1d?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/0295a707cd1d</guid>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Sun, 08 Feb 2026 11:33:00 GMT</pubDate>
            <atom:updated>2026-02-09T23:24:42.696Z</atom:updated>
            <content:encoded><![CDATA[<p>If you’ve ever used a real-time collaborative editor and thought, “<em>This feels like Git… somehow,</em>” you’re not wrong.</p><p>But here’s the twist: OT isn’t Git merge. And it’s not exactly Git rebase either.</p><p>Operational Transformation (OT) works like this: it <strong>rebases incoming edits automatically</strong>, one operation at a time, onto whatever state your document is currently in. After all sites replay the same rebased operations, everyone converges to a single shared result — basically a <strong>merge outcome</strong>, but without branches, conflict markers, or humans in the loop.</p><p>That’s why OT-powered collaboration feels “invisible”: the system does the annoying integration work continuously, so users never have to.</p><p>In this post, we’ll walk through the classic OTFAQ example (Figure 1) in plain developer terms, then use it to build a crisp mental model: <strong>rebase-like mechanics → merge-like outcome</strong>, <strong>fully automatic</strong>.</p><h3>The real problem OT solves</h3><p>Real-time collaboration is hard because users refuse to wait.</p><p>In a collaborative editor:</p><ul><li>every user has a local replica of the document,</li><li>edits happen concurrently,</li><li>operations arrive at different sites in different orders,</li><li>and users still expect everyone to see the same document.</li></ul><p>If you simply replay remote edits “as-is,” replicas diverge. That’s not a corner case — it’s guaranteed.</p><p>OT exists to make concurrent edits commute <strong>without delaying local interaction</strong>.</p><h3>The basic idea of OT (think: rebase)</h3><p>OT’s core idea is simple:</p><blockquote><strong>When a remote operation arrives, rewrite it so it can be applied on your current document state, even though it was created on a different one</strong>.</blockquote><p>That’s the intuition behind git rebase.</p><p>The following is the canonical OT example (Figure 1 in OTFAQ [1]).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/966/1*koN8Z4-xxLIQiMR6VQxMyA.png" /></figure><p>Two people are editing the same text, starting from the same content: <strong>abc</strong>.</p><p>One user inserts <strong>x</strong> at the very beginning. On their screen, the document instantly becomes <strong>xabc</strong>.</p><p>At the same time, the other user deletes the last character <strong>c</strong>. On their screen, the document instantly becomes <strong>ab</strong>.</p><p>So far so good — each person got instant local responsiveness. But now the edits cross the network.</p><p>Here’s the key problem: the delete was created against <strong>abc</strong>, not <strong>xabc</strong>. If it were applied “as-is” on the first user’s current document, it would delete the wrong character, because the earlier insertion shifted positions.</p><p>So OT does a <em>rebase</em>-like step: it adjusts the incoming delete so it still targets <strong>c</strong>, which has moved one position to the right. After applying that rebased delete, the first user’s document becomes <strong>xab</strong>.</p><p>On the other side, the insertion arrives at a document that’s already <strong>ab</strong>. Deleting the last character doesn’t affect position 0, so the insert doesn’t need adjustment. When it’s applied, the second user’s document also becomes <strong>xab</strong>.</p><p>Both replicas converge to the same final text: <strong>xab</strong>.</p><p>No locks. No conflict UI. No waiting. Just automatic “<em>rebase onto my current state</em>,” and the merge-like outcome drops out naturally.</p><h4>The correct mental model</h4><blockquote><strong><em>OT continuously rebases incoming edits; executing all rebased edits yields a merge-like result — fully automatically and invisibly.</em></strong></blockquote><p>If you keep that sentence in your head, OT suddenly stops feeling mysterious.</p><h3>OT vs Git: rebase mechanics → merge outcome</h3><p>The cleanest comparison is to separate <strong>mechanism</strong> from <strong>result</strong>. Most explanations fail because they collapse the two.</p><h4>OT does rebase as a mechanism</h4><p>When a remote operation arrives in an OT system, it was created on a different base document state. OT therefore <strong>rebases</strong> that operation onto the current local state by transforming it.</p><p>This rebasing step rewrites the operation’s parameters (for example, positions) so the operation can still achieve its intended effect on the new base.</p><p>This step is purely rebase-like. It is not choosing between edits. It is rewriting an edit so it still makes sense after other edits happened.</p><h4>OT achieves a merge outcome by execution</h4><p>After all sites have received the same set of operations, and rebased (transformed) each operation as needed, every site executes the transformed operations and converges to the same final document.</p><p>That final state includes the effects of all concurrent edits and is identical across replicas — what users perceive as “everything merged.”</p><p>This is a merge outcome, but not a merge mechanism.</p><h4>Why this distinction matters</h4><p>Git also has rebase and merge, but they live at different layers.</p><p>Git rebase rewrites commits onto a new base. Git merge combines histories and sometimes forces humans to resolve conflicts.</p><p>OT uses rebase mechanics to prevent conflicts from surfacing in the first place, and the merge outcome emerges naturally from execution.</p><p>A useful way to say it is: OT rebases operations so a merge outcome becomes inevitable. Git merges results and often asks humans to resolve conflicts when rebasing or merging gets ambiguous.</p><h4>Why OT feels invisible to users</h4><p>Git integration is explicit by design. Humans decide when to integrate, inspect conflicts, and resolve them.</p><p>OT removes that friction:</p><ul><li>there is no “merge now” action,</li><li>there are no conflict markers,</li><li>there is no manual resolution step,</li><li>integration happens per operation, often per keystroke.</li></ul><p>OT works at the semantic level of editor operations — adjusting parameters like positions. Because of that, most syntactic conflicts can be resolved deterministically by the system.</p><p>From the user’s perspective, collaboration “just works.”</p><h3>OT + Git: rebase live, merge later</h3><p>Seen this way, OT and Git aren’t competing models — they’re solving similar problems at <strong>different moments in time</strong>.</p><p>A practical way to combine them is to let each do what it’s best at: <strong>OT handles rebase mechanics in real time; Git records the merge outcome afterward</strong>. This is the path explored by <strong>ATCoPE</strong> [3]. Developers collaborate inside short-lived real-time sessions where OT continuously rebases incoming edits and keeps everyone converged, while Git remains the non-real-time system of record for history, branching, and review. When the real-time session ends, the OT-managed workspace is brought to a consistent state and committed back to Git as a single merge outcome.</p><p><strong>OT preserves flow. Git preserves history.</strong></p><h4>References</h4><p>[1] C. Sun, “<a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">OTFAQ: Operational Transformation Frequently Asked Questions and Answers.</a>”</p><p>[2] The Git Book: Rebasing — <a href="https://git-scm.com/book/en/v2/Git-Branching-Rebasing">https://git-scm.com/book/en/v2/Git-Branching-Rebasing</a>.</p><p>[3] H.F. Fan, C. Sun, and H.F. Shen, “ATCoPE: Any-Time Collaborative Programming Environment for Seamless Integration of Real-Time and Non-Real-Time Teamwork in Software Development”, <a href="https://dl.acm.org/doi/proceedings/10.1145/2389176">Proceedings of the 2012 ACM International Conference on Supporting Group Work</a>. Pages 107–116. <a href="https://doi.org/10.1145/2389176.2389194">https://doi.org/10.1145/2389176.2389194</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=0295a707cd1d" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[JSON as the Foundation Data Model for Co-Editing]]></title>
            <link>https://medium.com/@czsun08/json-as-the-foundation-data-model-for-co-editing-5622cdc6f493?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/5622cdc6f493</guid>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Tue, 07 Oct 2025 23:04:49 GMT</pubDate>
            <atom:updated>2026-01-27T11:39:48.906Z</atom:updated>
            <content:encoded><![CDATA[<h4>Add Real-Time Collaboration to Editors with JSON States</h4><p><a href="https://www.codox.io/">Codox</a> is a real-time collaboration API that that lets you turn any existing web editing application with <strong>a JSON-based state</strong> a multi-user collaborative application. Codox integrates with several popular frameworks and libraries, including:</p><ul><li><strong>Codox-Lexical</strong> — Co-editing with editors based on Lexical.js</li><li><strong>Codox-Draft</strong> — Co-editing with editors based on Draft.js</li><li><strong>Codox-Kanban</strong> — Real-time collaboration on Trello-style boards</li><li><strong>Codox-GoJS</strong> — Shared editing of charts, trees, and diagrams</li><li><strong>Codox-ToDo</strong> — Live collaboration on to-do lists</li><li><strong>Codox-AgGrid</strong> — Multi-user co-editing in AG Grid tables</li><li><strong>Codox-ReactTable</strong> — Synchronized editing with React Table</li></ul><p>At the heart of all these applications is a single unifying choice: <strong>JSON as the foundational document model. </strong>JSON’s simplicity and versatility make it an ideal backbone for both structured and unstructured content — from rich text and tables to trees, Kanban boards, data grids, and more. It’s already the <em>lingua franca</em> of modern web editors for <strong>file storage</strong> and <strong>data exchange</strong>. Codox extends that strength into the realm of <strong>collaborative editing</strong>.</p><p>Two core enabling technologies make this approach possible in Codox:</p><ol><li><strong>State Differentiation (SD)</strong> — to efficiently detect and represent changes between JSON-based document states.</li><li><strong>Operational Transformation (OT)</strong> — to merge concurrent changes (edits) from multiple users in real time (online) and non-real-time (offline).</li></ol><p>Together, State Differentiation and Operational Transformation form the technical foundation that allows any editor with a JSON-based state to evolve into a fully-fledged co-editor — with:</p><ol><li>A unified mechanism to capture and merge edits across diverse document types.</li><li>Straightforward integration with existing front-end editors without major API changes.</li><li>Real-time and offline collaboration with robust concurrency control.</li></ol><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tW3D3EToloAXw1G7tVUVqw.png" /><figcaption>The Three Pillars of JSON-Based Co-editing</figcaption></figure><p>Developers can explore these ideas directly through the <a href="https://app.codox.io/login">online demos</a> and <a href="https://docs.codox.io/">documentation</a> for practical API and integration examples.</p><p>In the remainder of this article, we go behind the scenes of the Codox API to examine how <strong>JSON-based document state</strong>, <strong>State Differentiation</strong>, and <strong>Operational Transformation</strong> work together to support rich-text co-editing, using <strong>Codox-Lexical</strong> as a running example.</p><h4>JSON-RT-state for Rich Text Editors</h4><p>Lexical maintains the state of an editor in memory and updates it in response to user input. It also provides APIs for serialising and deserialising this internal state to and from a JSON format. In this article, we refer to this JSON-encoded state as the <strong>JSON-RT-state</strong> (JSON Rich Text state), which serves as the foundation for both <strong>State Differentiation (SD-JSON-RT)</strong> and <strong>Operational Transformation (OT-JSON-RT)</strong> in Codox.</p><p>Fig. 1 demonstrates the UI-state of an example Lexical rich-text document, containing a single <strong>paragraph</strong> with formatted-texts and an embed <strong>image</strong>, a <strong>horizontal rule</strong>, a <strong>table</strong> with two-rows of two cells, a <strong>list</strong> with two list-items, and a <strong>sticky-note</strong> (with formatted text) positioned at the upper-right corner of the UI.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*02t13j1XnfdHWZagsfgs-w.png" /><figcaption>Fig 1. An example Lexical document UI-state.</figcaption></figure><p>Corresponding to the UI-state in Fig.1, the JSON-RT-state (see Fig. 2) of this Lexical document is represented as a hierarchical tree of data objects. The root object of the tree contains editor-specific properties and a children array that holds the document’s main structural elements, referred to as <strong>blocks. </strong>In this example, there are the five data blocks — aparagraph, achorizonalrule, atable, alist, and astickynote — each highlighted for clarity in the figure.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*SqfGEvd6W7UvqBzbZtiLbA.png" /><figcaption>Fig.2. The Lexical document JSON-RT-state corresponding to the UI-state in Fig.1.</figcaption></figure><h4>Data Blocks in a JSON-RT-state</h4><p>A JSON-RT-state can include many types of data blocks, with each type reflecting the functionalities, features, and design goals of the editor. Certain block types are particularly significant for collaborative editing. The following sections examines the main categories, starting with the Rich Text Block — the most fundamental.</p><h4>1. Rich Text Block</h4><p>A rich text block is a data object representing a range of stylised block content types — including <em>paragraphs</em>, <em>quotes</em>, <em>code</em> blocks, and more. This block serves as the <strong>foundation</strong> for representing and editing rich text, both for single-user and co-editing scenarios.</p><p>In the Lexical document UI-state (see Fig. 1), a rich text block is shown in a <strong>one-dimensional, linear space</strong>, meaning its content flows in a straight sequence, just like text in a paragraph.</p><p>Where can rich text blocks appear in a JSON-RT-state?</p><ul><li>At the <strong>top level</strong>, a rich text block may appear directly in the children array of the root object of a JSON-RT-state (for example, the paragraph at index 0 shown in Fig. 2).</li><li>Within <strong>hierarchical structures</strong>, rich text blocks may also be found in higher-level containers, such as table cells or list items.</li></ul><p>What does a rich text block contain?</p><ul><li>Each rich text block contains a children property — an array of <strong>rich text elements.</strong></li><li>A rich text element can represent a piece of formatted<em> </em>text, a hyper<em> </em>link, an embedded<em> </em>image, a code segment, and more.</li></ul><p>For instance, in Fig. 3, the data block at index 0 in the root’s children array is a paragraph rich text block. This block contains <em>15</em><strong> </strong>rich text elements, each with its own format, style and text values (highlighted in the figure). These elements collectively represent the visible and editable content of the paragraph in the UI-state.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*FErDJFbcsp5LOCtaR5eCBA.png" /><figcaption>Fig.3. An example paragraph rich text block with 15 elements, including formatted texts, link, code, image, etc.</figcaption></figure><p>There is also a special category of rich text elements<strong> </strong>known as <strong>embed elements</strong>. Unlike text, an embed element contains its own <strong>nested </strong>JSON-RT-state, which is itself editable. In Lexical, embed elements may represent <em>images</em>, <em>polls</em>, and <em>equations</em> within rich text blocks. For instance, the rich text element at index 13 of the paragraph block’s children array is an <strong>embedded image </strong>(indicated in Fig. 3). Its internal, editable structure is illustrated in Fig. 4.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qTaZXap1dksAquGi2MiEMA.png" /><figcaption>Fig. 4 An example of nested JSON-RT-state in an embed image in a paragraph of Lexical.</figcaption></figure><p>One key detail is how embed elements appear in the document UI-state:</p><ul><li>An embed element (e.g., an <em>image</em>) occupies <strong>a single position</strong> in the paragraph’s linear sequence.</li><li>Any attached content, such as rich text paragraphs in a <em>caption</em>, belongs to the <strong>nested JSON-RT-state</strong> inside the embed element.</li></ul><p>In a co-editing setting, multiple users can edit different parts of the same embed element at the same time — for example, adjusting its <em>height</em> and <em>width</em>, while also modifying the rich-text <em>caption. </em>This introduces challenges in merging concurrent edits correctly, as we elaborate in later sections.</p><h4>2. Hierarchical Block</h4><p>A hierarchical block is a data object that acts as a container for other structures, representing content organised with <strong>nested structure,</strong> such as <em>tables</em> or <em>lists</em>. In Lexical, hierarchical blocks always have a children array, where each child can itself be another hierarchical block or a rich text block. This nesting enables complex document structures to be represented within the JSON-RT-state.</p><p>In the document UI-state (see Fig. 1), hierarchical blocks occupy a <strong>multi-dimensional space</strong>, unlike rich text blocks, which are represented as one-dimensional linear spaces.</p><p><strong>Example 1: Table</strong></p><p>A <strong>table </strong>is a nested structure represented by a hierarchical block.</p><ul><li>It contains a sequence of <strong>table-row blocks.</strong></li><li>Each table-row is itself a hierarchical block containing <strong>table-cell blocks</strong>.</li><li>Each table-cell is again a hierarchical block containing one or more rich text blocks (e.g., paragraphs).</li></ul><p>In the Lexical JSON-RT-state (see Fig. 5), the data block at index 2 in the root’s children array is a table hierarchical block. It contains two tablerows; each row has two tablecells, and each cell contains one paragraph.</p><p>In a co-editing scenario, multiple users can concurrently:</p><ul><li>Insert, delete, or move entire tables within the root children array.</li><li>Insert or delete table rows or columns (a column is represented as all table-cells at the same column index across rows).</li><li>Edit the rich text inside table cells.</li><li>Merge or un-merge adjacent table cells.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5lCYHRvIeHCV7uQrCc80Mg.png" /><figcaption>Fig.5. An example Lexical JSON-RT-state with a table, table-rows, table-cells, and paragraphs.</figcaption></figure><p><strong>Example 2: List </strong><br>Lists are another type of hierarchical block, containing an ordered sequence of list items. Each list item can itself be nested, holding additional lists or other block types.</p><p>In the Lexical JSON-RT-state (see Fig. 6), the data block at index 3 in the root’s children array is a list<strong> object</strong> . This list has two list items, and each item contains two paragraphs. Moreover, a list item may contain a <strong>nested </strong>list as well.</p><p>In co-editing, users can concurrently:</p><ul><li>Insert, delete, or move entire lists within the root children array.</li><li>Insert or delete list items within a list.</li><li>Edit rich-text content inside any list item.</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*H4Z3i9NMT-74I8LJ3r9hjQ.png" /><figcaption>Fig.6. An example <strong>list</strong> hierarchical block, with two <strong>list items</strong>, and two <strong>paragraphs</strong> in each list item in a Lexical JSON-RT-state.</figcaption></figure><p>Beyond tables and lists, hierarchical blocks may also represent more complex components in Lexical, such as <em>Excalidraw</em>, <em>Columns Layout</em>, <em>Collapsible container</em>, etc.</p><p>We illustrate and elaborate some of the issues on how to handle concurrent operations in hierarchical blocks in Section <strong>OT-Powered Concurrency Control for JSON-RT-Ops.</strong></p><h4>3. Embed Block</h4><p>In modern editors, embeds are first-class blocks that integrate diverse external data — such as videos, charts, or figures — directly into the document. They display live previews, define their own schema, and serialize cleanly (for example, as JSON), allowing documents to serve as interactive workspaces without requiring users to switch context.</p><p>Some embeds may render content that is directly editable within the editor, while others render read-only content. For editable embeds in Lexical, the data exists only in the children array of the root object and contains a <strong>nested editable</strong> JSON-RT-state. This nested state can host additional rich text content and related properties.</p><p>An example of an embed block in Lexical is the <em>sticky note.</em> The data block at index [4] in the root’s children array is a stickynote<strong> </strong>block, which contains its own internal JSON-RT-state for both formatted text and block-specific properties (e.g., xOffset, yOffset).</p><p>During co-editing, multiple users can:</p><ul><li>Insert, delete, and move an entire embed block within the root’s children array,</li><li>Edit or format texts inside its nested JSON-RT-state,</li><li>Update block-specific properties (e.g., the <em>position</em> or <em>color</em> of a <em>sticky-note</em>).</li></ul><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dV3mMjS-R6jkUaV_yxVWvw.png" /><figcaption>Fig. 7. <strong>Sticky-note</strong> as an example editable embed block, with a nested JSON-RT-state internal structure.</figcaption></figure><p>The key distinction between an embed block and an embed element is their placement and role:</p><ul><li>An <strong>embed block (</strong>e.g. a <em>sticky-note</em><strong>) </strong>always lives directly under the root object.</li><li>An <strong>embed element</strong> (e.g., an <em>image</em> inside a paragraph) may appear inside any rich text blocks.</li></ul><h4>4. Atomic Block</h4><p>Non-editable document structures or read-only embeds are represented as atomic blocks. Atomic blocks have no internal editable state and are treated as indivisible units — they can only be inserted, deleted, or moved within the document, but cannot be modified internally.</p><p>In Lexical, an atomic block can only exist in the children<strong> </strong>array of the root object and has no editable internal structure. Examples of UI and document components that are represented as atomic blocks include: <em>horizontal rule, page break, YouTube embed, tweet embed</em><strong>, </strong>etc.</p><p>Although atomic blocks cannot be edited internally, they can be inserted, deleted, or moved within the root’s children array. In co-editing, multiple users can perform these operations concurrently. If two users try to delete or move the same atomic block simultaneously, conflict resolution ensures only one operation succeeds.</p><p><strong>Example:</strong><br>The data block at index [1] in the root’s children array is a horizontal rule — an atomic block with no internal JSON-RT-state, as shown in Fig. 8.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oeu8u5U7UwqfngzhegIuwQ.png" /><figcaption>Fig. 8. The horizontal rule as an example atomic block at index 1 of the children array of the root.</figcaption></figure><p><strong>Summary</strong><br>Codox operates on rich-text documents represented as a <strong>JSON-RT-state</strong>, in which all editable sequential and nested structures — such as paragraphs, lists, and tables — are modeled as well-defined JSON blocks. This JSON-based representation enables developers to add collaboration to editors built on frameworks, such as Lexical.js or Draft.js, that expose their internal state as JSON — without altering the core document model or hooking into low-level node mutation logic. The JSON-RT-state serves as the foundational data model for both <strong>State Differentiation (SD-JSON-RT)</strong> and <strong>Operational Transformation (OT-JSON-RT)</strong>, which are discussed in the following sections.</p><h4><em>Differentiation </em>for JSON-RT-states</h4><p>A key technical component of Codox API is the <em>State Differentiation (SD) scheme</em> for JSON-RT-states (<strong>SD-JSON-RT)</strong>.</p><p>For brevity, we use the following terms:</p><ul><li><em>BState </em>for<em> </em>the document JSON-RT-state <em>before</em> a user applies edits</li><li><em>AState</em> for<em> </em>the document JSON-RT-state <em>after</em> the edits are applied.</li></ul><p>The SD-JSON-RT scheme takes a pair of states (BState, AState) and derives the differences between them. These differences are represented as a sequence of JSON-RT operations (<strong>JSON-RT-Ops</strong>):</p><pre>SD-JSON-RT(BState, AState) = JSON-RT-Ops</pre><h4>Requirements for SD-JSON-RT</h4><p>The SD-JSON-RT scheme must meet three fundamental requirements: <strong>correctness</strong>, <strong>intention-preservation</strong>, and <strong>OT-compliance</strong>.</p><h4>1. Correctness</h4><p>The scheme is <strong>correct</strong> if the derived operations JSON-RT-Ops can faithfully transform the before-state (<em>BState</em>) into the after-state (<em>AState</em>):</p><pre>Apply-JSON-RT(JSON-RT-Ops, BState) = AState</pre><p>Here, Apply-JSON-RT is an internal module that applies JSON-RT-Ops to a given JSON-RT-state and produces another JSON-RT-state.</p><h4>2. Intention-Preservation</h4><p>Beyond the basic correctness, the scheme must also preserve the <strong>intended effects</strong> of user edits. We call this <strong>intention-preservation</strong>.</p><p>Informally, intention-preservation requires that the derived JSON-RT-Ops capture precisely the user’s intended modifications when converting <em>BState</em> into <em>AState</em>. This means not only reflecting the changes to the <strong>target objects</strong> (being <em>inserted, deleted, updated</em>, or <em>moved </em>object) but also ensuring unrelated objects remain unchanged. In other words, intention-preservation is as much about what changes <em>do</em> happen as about what <em>doesn’t</em>.</p><p><strong>Examples:</strong><br>If a user moves an object from one position to another, intention-preserving JSON-RT-Ops should express <em>only</em> that move. If instead the scheme encodes the edit as “<em>delete everything in BState, then insert everything in AState</em>,” the result is <em>correct</em> (since <em>BState</em> → <em>AState</em>) but not intention-preserving, because it obscures the specific user intent and affects unrelated objects.</p><p>Intention-preservation also implies <em>fine-grained</em> operation derivation. For instance, suppose a user applies multiple edits in the document UI-state, to change &quot;1234567890&quot; into &quot;1<strong>2345</strong>6a7b8c9&quot; (e.g. during the offline editing mode):</p><p>1. apply <strong>Bold</strong> to 2345</p><p>2. insert a after 6</p><p>3. insert b after 7</p><p>4. insert c after 8</p><p>5. delete 0 after 9</p><p>To preserve intended effects of these edits, the derived JSON-RT-Ops must encode <em>exactly</em> these fine-grained edits. This granularity becomes essential in merging the effects of concurrent JSON-RT-Ops (see Section <strong>OT-Powered Concurrency Control for JSON-RT-Ops</strong>).</p><h4>3. OT-compliance</h4><p>Finally, the scheme must be <strong>OT-compliant</strong>. In practice, this means that JSON-RT-Ops must be directly suitable for use in Operational Transformation (OT), underpinning concurrency control for co-editing.</p><p>To fully leverage OT for <strong>fine-grained conflict resolution</strong>, JSON-RT-Ops must correctly address any data objects within the hierarchical structure of a JSON-RT-state. Each operation must precisely locate its target in this multi-level structure and remain valid under concurrent actions — even when other users are editing nearby or nested elements.</p><p>This poses particular challenges when dealing with <strong>deeply nested data</strong>, such as rich text elements and object properties (e.g., image size, or position) within paragraphs, lists, or tables, or residing inside <em>nested</em> JSON-RT-states.</p><h4><strong>Summary</strong></h4><p><strong>SD-JSON-RT</strong> in Codox provides a general and efficient way to derive and represent changes between JSON-RT-states. Instead of transmitting entire document snapshots, SD-JSON-RT pinpoints only the modified segments — whether structural changes, property updates, or deep rich text edits inside embedded data blocks — and encodes them as JSON-RT-Ops for OT-based concurrency control. These operations are:</p><ul><li><strong>Correct</strong> — faithfully transform <em>BState</em> into <em>AState.</em></li><li><strong>Intention-preserving</strong> — capture exactly what the user edits intended, no more, no less.</li><li><strong>OT-compliant</strong> — ready to participate in operational transformation and concurrent editing.</li></ul><p>To our knowledge, Codox’s <strong>SD-JSON-RT</strong> is the only state differentiation scheme capable of deriving correct, intention-preserving, and OT-ready operations from JSON states alone. This enables Codox apps to capture precise, fine-grained user edits while avoiding the complexity and fragility of instrumenting low-level editor node mutations.</p><h4>OT-Powered Concurrency Control for JSON-RT-Ops</h4><p>Codox API is powered by high-performance <strong>collaboration engine</strong> built on state-of-the-art Operational Transformation (OT) technologies. This engine contains three major components:</p><ol><li><strong>OT-JSON-RT transformation functions</strong> — handle concurrent JSON-RT-Ops to ensure that edits from multiple users are properly combined.</li><li><strong>Distributed OT control algorithms</strong> — control the transformation process without replying a central server, enabling fully decentralised collaboration.</li><li><strong>Advanced OT techniques</strong> — ensure both real-time (online) and non-real-time (offline) collaboration, supporting work during intermittent or lost connectivity.</li></ol><p>In the following, we focus on the <strong>OT-JSON-RT transformation functions</strong>, which are directly relevant to JSON-RT-Ops. For details on distributed OT control algorithms and online/offline co-editing, readers are referred to [2,3,4].</p><h4>Combined Effects for Concurrent JSON-RT-Ops</h4><p>In a collaborative editing, multiple users may modify any parts of a shared document (represented as a JSON-RT-state) at the same time. These concurrent edits can sometimes overlap or come into conflict. <strong>OT-JSON-RT </strong>is a core component of the Codox API, providing concurrency control and conflict resolution to ensure that all edits are correctly merged.</p><p>The following sections outline how <strong>OT-JSON-RT</strong> handles the <em>combined effects</em> of representative JSON-RT-Ops, illustrated with concrete examples. For those interested in exploring further, we encourage trying the online <a href="https://app.codox.io/login">Codox Apps demo</a> (e.g., <strong>Codox-Lexical</strong>) to see these effects in action and to gain hands-on exposure on how we maintain user edit correctness and intention-preservation under concurrency.</p><p><strong>Rich Text Editing Operations</strong><br>Rich text editing operations include <em>inserting</em>, <em>deleting</em>, and <em>updating</em> rich text inside a <strong>rich text block</strong>, such as a paragraph, a table cell, or a list item.</p><ul><li><strong>Edits in different blocks.</strong><br>When multiple rich text edits happen in different data blocks (e.g., different paragraphs, table cells, or list items), they are <em>independent</em> and therefore <em>compatible</em>. In this case, <strong>OT-JSON-RT</strong> simply apples all edits as they are, and the combined effect is the union of all edits.</li><li><strong>Edits in the same block.</strong><br>When multiple edits affect the same block, their ranges or properties may overlap or conflict. Here, <strong>OT-JSON-RT</strong> transforms the operations so that the final state merges the effects of all edits.</li></ul><p>Fig. 9 illustrates the combined effect of two concurrent operations that update overlapping text attributes under <strong>OT-JSON-RT</strong>. In practice, some co-editing applications struggle to merge such overlapping updates reliably and often fail to handle even these seemingly straightforward cases consistently.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*2a-Ookr3M0nhV_sJmT0ijQ.png" /><figcaption>Fig. 9. An example combined effect for a pair of concurrent and overlapping attributes <em>update</em> operations.</figcaption></figure><p><strong>JSON Editing Operations</strong><br>JSON editing operations may update object properties (e.g., the <em>height</em> and <em>width</em> of an <em>image</em>, or the <em>color</em>, <em>xOffset</em>, and <em>yOffset</em> of a <em>sticky-note</em>), or modify the block structure of a JSON-RT-state, including but not limited to:</p><ul><li>Inserting, deleting, or moving a rich text block (e.g., a <em>paragraph</em>), a hierarchical block (e.g., a <em>table</em> or <em>list</em>), an embed block (e.g., a <em>sticky-note</em>), or an atomic block (e.g., a <em>page break</em>) within the children array of the root object in a JSON-RT-state.</li><li>Inserting or deleting a <em>table row </em>or <em>column</em> in a <em>table</em>.</li><li>Inserting or deleting a <em>list item</em> in a <em>list</em>, and similar structural changes.</li></ul><p>When multiple JSON edits occur concurrently, they may be independent (compatible) or dependent (conflicting):</p><ul><li><strong>Concurrent property-updating JSON edits:</strong> If multiple edits target the same set of object properties (e.g., <em>height</em> and <em>width</em> of an <em>image</em>), they are conflicting. Under <strong>OT-JSON-RT, </strong>conflict resolution<strong> </strong>ensures a single “winning” update, guaranteeing convergence across all co-editing sites. If they target different properties, the edits are compatible and can be executed <em>as-is</em>, preserving all effects.</li><li><strong>Concurrent structure-changing JSON edits:</strong> Compatibility depends on multiple factors, one of the most important being the address relationships among their target objects in the JSON-RT-state. Under the <strong>SD-JSON-RT</strong> scheme, each derived JSON-RT-Op carries an address path, representing the sequence of objects from the root to the target, expressed as an array of keys or array indexes.</li></ul><p>For comprehensive discussions on address path issues, readers are referred to [1] (pages 557–561) in the context of the XOTDM (eXtended OT Data Model) tree, which parallels the JSON-RT-state tree. In the following, we illustrate some concrete and representative scenarios involving four structure-changing JSON edit operations — O1, O2, O3, and O4 — as shown in Fig. 10.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*tjmI6V4M3gMILFf_ox08Qg.png" /><figcaption>Fig. 10. Illustration of four concurrent structure-changing JSON edit operations O1, O2, O3, and O4, and their address path relationships in a JSON-RT-state.</figcaption></figure><p><strong>Scenario 1 </strong>— <em>Ancestor–descendant conflict (move + edit inside the moving object) </em>Consider two operations, O1 and O2, in Fig. 10. O2 moves a table (at address path2 = [root, children, 2]) to a different address (not shown in Fig. 10) in the JSON-RT-state, while O1 inserts a new row (at address path1 = [root, children, 2, children, 1]) into that same table being moved by O2. In this case, the target object of O2 (the table) is an <em>ancestor block</em> of the target object of O1 (a row inside the table), because path2 is a prefix of path1.</p><p>This creates an <strong>address conflict</strong>: O2 changes the address of the table in which O1 is operating. When O1 is executed after O2, it must be <em>transformed</em> against O2 so that its address path is adjusted to the new location of the table. This ensures that the effects of both O1 and O2 are preserved under <strong>OT-JSON-RT</strong>.</p><p>This combined effect between a <em>move</em> operation (O2) and another operation (O1) is general and applies whenever O1 is any edit (e.g., a rich text edit or a property-updating JSON edit) inside a data block moved by O2 under <strong>OT-JSON-RT</strong>. For example, if O1 is a rich text edit to insert, delete, or update rich text inside a table cell of the table moved by O2, both operations will still be preserved.</p><p>It is worth emphasising that this combined effect is only possible because <strong>OT-JSON-RT</strong> supports a <strong>genuine move </strong>operation: deleting the target object from its original address and inserting it into a new address as a <em>single atomic action</em>. This differs from a <strong>fake move</strong>, which simulates a move as two <em>separate</em> edits — first a delete, then an insert.</p><p>If only fake moves were supported, the edits performed by O2 in the above scenario would be lost (removed by the separate delete operation in the fake move). Unfortunately, this is the behavior of many existing co-editing applications. The consequences can be severe. For instance, if O2 represents a large batch of edits accumulated while a user was offline (potentially over hours or days), and another user performs O1 (moving the same data block to a different place in the document) at any point during that time — making <strong>O₁</strong> and <strong>O₂</strong> concurrent — then, upon merging, <em>all</em> of the offline user’s edits could be lost.</p><p><strong>Scenario 2 </strong>— <em>Independent edits (no conflict)</em>.<strong> </strong>Consider O1 and O4 in Fig. 10. Here, O1 is the same as in Scenario 1, while O4 deletes a list item from a list at address path4 = [root, children, 3, children, 0] in the JSON-RT-state. In this case, the two operations are <em>compatible</em> because they target different objects and there is no address conflict (neither path1 nor path4 is a prefix of the other). O1 and O4 require no transformation against each other, and both effects are preserved.</p><p>This combined effect is not unique to O1 and O4 — it is a general property of <strong>OT-JSON-RT</strong>. Whenever two edits (e.g., rich text edits or property-updating JSON edits) target different objects without address conflicts, they can safely coexist. For instance, if O1 is a rich text edit to insert, delete, or update text inside a table cell, while O2 is an RT-edit to insert, delete, or update text in a list item, both edits will be executed as-is and all effects are preserved under <strong>OT-JSON-RT</strong>.</p><p><strong>Scenario 3 </strong>— <em>Move the same object to different destinations </em>(<em>move vs move</em>). This scenario involves O2 and O3 in Fig. 10. Both operations attempt to move the same table at path2/path3 = [root, children, 2], but to <em>different</em> destinations (not shown in Fig. 10): for example, O2 moves the table to the position after the list, while O3 moves it to the position before the horizontal rule. In this case, the two operations are in <em>direct conflict</em> because they both target the same object (the table) but specify different destination addresses.</p><p><strong>OT-JSON-RT</strong> resolves this conflict by designating one operation as the <em>winner</em>, ensuring that all co-editing sites converge to the same final state. By contrast, if fake-move semantics were used, the combined effect would remove the table from its original location and then <strong>duplicate</strong> it into both destination addresses (due to the two separate inserts in the two fake-move operations)— a problem that, unfortunately, occurs in many existing co-editing systems.</p><p><strong>Summary</strong><br>Concurrency control in Codox is built on <strong>OT-JSON-RT</strong>, which ensures that concurrent JSON-RT operations — whether inserts, deletes, moves, or rich-text attribute updates — are merged into a consistent document state. Independent operations are preserved without change, address conflicts (e.g., ancestor–descendant edits) are resolved through transformation, and true move semantics prevent data loss or block duplication. When rich text edits overlap within the same block, OT-JSON-RT transforms them so that all effects are merged and preserved. The result is predictable, intention-preserving, and convergent outcomes that let multiple users safely co-edit the same JSON-based document in real time or asynchronously.</p><h3>The Future of Co-Editing</h3><p>Co-editing is no longer a <em>“nice-to-have”</em> feature — it’s an expectation. Yet most web-based editors were never designed with collaboration in mind. <strong>Codox bridges this gap</strong> with a unified, JSON-based foundation data model, powered by <strong>State Differentiation (SD-JSON-RT)</strong> and <strong>Operational Transformation (OT-JSON-RT)</strong>.</p><p>With Codox, <strong>rich-text co-editing in JSON documents has evolved beyond academic theory</strong> into <strong>proven, production-ready technology</strong> — already powering live applications where users collaborate in both real time and asynchronously, with predictable and consistent results.</p><p>The principles demonstrated through <strong>Codox-Lexical</strong> extend naturally to any editor with JSON-based document state, paving the way toward a <strong>common framework for interoperable, fine-grained, and conflict-free collaboration</strong> across the modern web editing ecosystem.</p><p>The future of collaborative apps is here. And with Codox, you don’t need to reinvent the wheel — you can <strong>plug collaboration directly into the editors your users already love</strong>.</p><p>If you’re building or extending a collaborative application, the fastest way to get started is to try<strong> </strong><a href="https://app.codox.io/login"><strong>the live demos</strong></a> (e.g., Codox-Lexical, Codox-Kanban, Codox-AgGrid) and see the results of <strong>SD-JSON-RT</strong> and <strong>OT-JSON-RT</strong> in action. Then dive into the <a href="https://docs.codox.io/"><strong>online documentation</strong></a> to learn how to use Codox APIs and services to make your own JSON-based editor collaborative — instantly.</p><h4>References</h4><p>[1]. C. Sun, S. Xia, D. Sun, D. Chen, H. Shen, W.T. Cai. <a href="https://dl.acm.org/doi/10.1145/1188816.1188821">Transparent adaptation of single-user applications for multi-user real-time collaboration.</a> <a href="https://dl.acm.org/toc/tochi/2006/13/4">ACM Transactions on Computer-Human Interaction (TOCHI), Volume 13, Issue 4</a> (2006). Pages 531–582.</p><p>[2]. Y. Xu and C. Sun. <a href="https://ieeexplore.ieee.org/document/7060680">Conditions and Patterns for Achieving Convergence in OT-based Co-Editors.</a> IEEE Transactions on Parallel and Distributed Systems ( Volume: 27, Issue: 3, 01 March 2016).</p><p>[3] D. Sun, C. Sun, Agustina, W. Cai. “<a href="https://arxiv.org/abs/1905.01517">Real differences between OT and CRDT in building co-editing systems and real-world applications</a>,” May 2, 2019.</p><p>[4]. C. Sun, <a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">“OTFAQ: Operational Transformation Frequently Asked Questions and Answers.”</a></p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=5622cdc6f493" width="1" height="1" alt="">]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Debunking Myths and Unveiling Facts: OT vs. CRDT in Distributed and Peer-to-Peer Co-Editing]]></title>
            <link>https://medium.com/codox/debunking-myths-and-unveiling-facts-ot-vs-crdt-in-distributed-and-peer-to-peer-co-editing-c4bfd1527ab5?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/c4bfd1527ab5</guid>
            <category><![CDATA[distributed-co-editing]]></category>
            <category><![CDATA[peer-to-peer-co-editing]]></category>
            <category><![CDATA[ot-vs-crdt]]></category>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Tue, 02 Jul 2024 05:42:58 GMT</pubDate>
            <atom:updated>2026-01-27T11:41:14.487Z</atom:updated>
            <content:encoded><![CDATA[<p>In the co-editing community, there have been recurrent claims that CRDT (Commutative Replicated Data Type) holds the key to distributed co-editing and is often touted as a major differentiator and superior to OT (Operational Transformation) for facilitating “peer-to-peer co-editing” or “p2p co-editing.” A common argument used to support these claims is that OT requires a central server, as exemplified by platforms like Google Wave/Docs, whereas CRDTs appear to operate without such a server. However, these claims are not only factually incorrect but also highly misleading, causing significant confusion within the co-editing community, especially among newcomers.</p><p>These misconceptions stem from various factors, including a general lack of knowledge of distributed co-editing, and repeated creation and spread of false information. Even experienced industrial engineers and open-source practitioners who have developed practical OT-based co-editing products or crafted useful transformation functions often lack awareness or have limited knowledge that OT can function perfectly without relying on a central server. This misunderstanding has led some to believe that their OT systems are restricted to operating with a central transformation server, like Google Wave/Docs, thereby significantly underestimating the true value of their own work.</p><p>This article aims to dispel these common myths and misconceptions and shed light on the factual aspects of distributed and p2p co-editing. By addressing these misunderstandings, we seek to provide much-needed clarity and drive significant advancements in co-editing technology for real-world applications.</p><h3>Myths and Facts in P2P Co-Editing</h3><p>In co-editing literature, the term “p2p co-editing” is rather ambiguous and tends to encompass multiple factors. Therefore, in this article, I will dissect and examine these factors individually, clarifying their relationships with OT and CRDT solutions in the following subsections.</p><h4>Constraints on operation propagation</h4><p>Both OT and CRDT solutions in co-editing share a common requirement: editing operations must be executed in their causal-effect orders, ensuring causality preservation. This order is based on the <em>happen-before</em> relation and is achieved through suitable distributed computing techniques, whether using client-server or peer-to-peer models, which are orthogonal to OT or CRDT.</p><p>Some CRDT solutions, like WOOT variations, deviate from the general causal ordering condition and impose WOOT-specific execution conditions. In WOOT, an operation is accepted for execution only if the neighboring objects (for an insert) or the target object (for a delete) already exist in the internal object sequence of the target replica. While this may be touted as an advantage for supporting p2p co-editing, these specific conditions cannot ensure the required causality preservation for co-editors and are computationally expensive to check.</p><p>On the other hand, all other CRDT solutions such as RGA and Logoot variations, along with OT solutions, adhere to the general causal ordering condition. Hence, except for WOOT variations, causally-ordered operation propagation and execution are common requirements shared by both OT and CRDT solutions, disqualifying them as a differentiating factor between the two.</p><h4>Requirement for a central server</h4><p>CRDT solutions do not explicitly require a communication <em>server</em>, but all, except WOOT (and its variations), assume the existence of an external causal-order-preserving communication <em>service</em>. However, the specifics of this service, such as required control information (e.g. timestamping) and whether any server is involved in implementing it, are left unspecified.</p><p>On the other hand, some OT solutions, such as Jupiter-OT, NICE, and Google Wave and Docs, explicitly require a transformation-based server to perform part of the transformation and broadcast operations, which are are known as <em>server-based</em> OT solutions (SOT). These SOTs are often cited by CRDT proponents to assert that OT is reliant on servers.</p><p>However, the majority of OT solutions, including adOPTed, GOT, GOTO, SOCT2, TIBOT, COT, and POT, do not require a central server to perform any part of the transformation work, which are known as <em>server-less</em> or distributed OT solutions (DOT). Instead, they rely on an external causal-order-preserving communication service, which is essentially the approach followed by most CRDT solutions.</p><p>The requirement of a server is merely a feature of individual solutions, rather than a general factor for differentiating OT and CRDT. In fact, OT offers co-editing system developers the flexibility to choose between server-based or fully distributed solutions, allowing them to tailor their systems to specific co-editing needs. The prevalent client-server architecture seen in existing co-editing systems primarily supports various aspects of co-editing, such as shared document storage, session management, message communications, and optionally running server-side OT algorithms if a server-based OT is chosen. Ironically, despite frequent claims that CRDT was invented for p2p co-editing, most CRDT-based co-editors are actually built using a client-server model.</p><h4>Vector-based vs scalar timestamping</h4><p>Yet another factor sometimes mentioned in connection to p2p co-editing is whether vector-based (with one element for each of co-editing sites in a session) or scalar-based (with a fixed number of variables, which is independent of the number of co-editing sites) timestamping or control is used in OT or CRDT solutions. However, both vector-based and scalar-based approaches have been utilized in OT and CRDT solutions, making this aspect non-distinguishing between the two.</p><p>For instance, the RGA solution employs vector-based timestamps to reduce time complexity, whereas Logoot and its variations use variable length object identifiers with an external causally-ordered broadcasting service.</p><p>On the other hand, some OT solutions, like adOPTed, GOT, GOTO, and COT, utilize vector-based timestamps, while other OT solutions, such as Jupiter-OT, NICE, TIBOT, SOCT4, Google Wave and Docs, and POT, employ scalar-based timestamps. In reality, scalar-based timestamping had already been in use in OT solutions long before the first CRDT (WOOT) came into being.</p><h4>Asserting CRDT’s Superiority in P2P Co-Editing is a Fallacy</h4><p>To summarise (see Table 1. Readers can find cited references in the table from [1]), all key factors related to p2p co-editing, including the requirement for a central server, causally ordered communication, and vector/scalar timestamping, are independent of whether an approach is based on OT or CRDT. These factors are merely characteristics of individual solutions, and they do not serve as general differentiators between OT and CRDT. Therefore, the assertion that CRDT has superiority in supporting p2p co-editing is a fallacy.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*qH3btBnYZiywrefneOrdsQ.png" /></figure><h3>Misconceptions Around Distributed OT Solutions</h3><p>Despite the prevalence of distributed OT solutions, certain misconceptions continue to cloud the understanding of this technology. These misconceptions include:</p><ol><li>Distributed OT solutions inherently require transformation functions to maintain specific transformation properties, such as CP2 (or TP2), which has been known to lead to certain complications.</li><li>Distributed OT solutions must utilize vector-based timestamping, which has been considered less suitable for p2p co-editing.</li></ol><p>To debunk these misconceptions, a few counter-examples suffice. For instance, both POT and TIBOT/TOBOT2.0 function as distributed (server-less) OT solutions that (1) do not require their combining transformation functions to preserve CP2, and (2) employ scalar timestamping instead of vector-based timestamping.</p><p>For more details and references on distributed co-editing and p2p co-editing, readers are referred to Section 2.3, titled “<strong>Architectures and Communication Topologies of OT-based Co-Editors</strong>”, and Section 4, titled “<strong>Myths and Facts about Peer-to-Peer Co-Editing</strong>”, in [1].</p><h3>Misconceptions in Commutativity</h3><p>Another misconception pertaining to p2p co-editing revolves around the way OT and CRDT achieve commutativity among concurrent operations within co-editing systems.</p><h4>CRDT’s native commutativity</h4><p>CRDT has often been portrayed as a data type or solution that guarantees “<em>concurrent operations commute with one another</em>.” However, the concept of commutativity was not a new one in co-editing, as OT had long been recognised for its capability to make concurrent editing operations commutative in replicated documents, a decade before the emergence of CRDT.</p><p>To distinguish CRDT from OT, proponents of CRDT put forth a <em>native commutativity</em> argument that can be summarised as follows: unlike OT, which achieves commutativity through transformation <em>after the fact</em>, CRDT makes concurrent operations <em>natively</em> commutative, thereby circumventing inconsistency and conflict issues by design. On top of the <em>native commutativity </em>argument, they further claim the CRDT approach is conflict-free and hence simpler than dealing with conflicts post facto, as OT does.</p><p>However, this CRDT’s supposed native commutativity is, in reality, a misconception, akin to “<em>the emperor’s new clothes</em>” in co-editing. The truth is that none of the core components within CRDTs, including internal object structures and sequences (with or without tombstones), immutable identifier-based operations, and object sequence search and manipulation schemes, are native to any editors.</p><p>Furthermore, CRDT is unable to circumvent the issue of position shifting or overlapping conflicts in text co-editing, despite its use of immutable identifier-based operations. Instead, CRDT must address the same inconsistency issues and make position-based concurrent operations commutative through transformation, albeit <em>indirectly</em> with significantly higher complexity than OT [2, 3].</p><h4>CRDT’s general commutativity</h4><p>In the ongoing discourse about CRDT native commutativity, a new variant of the CRDT commutativity argument has emerged, suggesting that: “<em>The OT algorithm allows concurrent operations to be reordered through rules that are more restrictive than the general commutativity used by CRDTs .</em>”</p><p>This CRDT <em>general commutativity </em>argument is notably vague. It provides no clues into why OT-supported commutativity is purportedly more restrictive than CRDT-supported commutativity and how any presumed distinctions in commutativity between OT and CRDT might affect co-editing solutions and practical applications. Furthermore, the proponent of this argument appears to be unaware of the existence of numerous OT solutions capable of achieving commutativity among concurrent operations without the need for reordering, let alone imposing specific reordering rules.</p><p>This is yet another instance of a recurring pattern in the generation and spread of misconceptions within the co-editing field: some individuals conduct cursory investigations using a limited set of examples and hastily extrapolate their findings. This, in turn, leads to unfounded sweeping claims, such as the false assertions that OT solutions universally depend on a central server, achieve commutativity through reordering concurrent operations, and generally suffer from a text-interleaving problem (based on misinterpretations of a few OT solutions [6]).</p><h3>Facts About OT-Enabled Distributed Co-Editing</h3><p>Historically, the first OT solution, named dOPT (distributed OPerational Transformation), emerged in 1989 as a distributed optimistic concurrency control solution for plain-text co-editing, without requiring a central server. While a few server-based OT solutions like JUPITER-OT (1995), NICE (2002), and GOOGLE-OT (2008) followed in subsequent years, the majority of OT solutions, including adOPTed (1996), GOT (1997), SOCT (1997), GOTO (1998), TIBOT (2004), COT (2006), and POT (2016), have continued the distributed nature of dOPT, functioning as distributed OT solutions.</p><p>Over the course of my personal involvement in co-editing since the 1990s, I and my collaborators have designed and published a diverse array of OT solutions. These solutions include both (server-less) distributed and server-based approaches, such as the generic control algorithms GOT (distributed), GOTO (distributed), NICE (server-based), COT (distributed), TIBOT (distributed) and TIBOT2.0 (distributed), and POT (distributed), along with application-specific transformation functions catering to various data types, ranging from plain-text to rich-text, JSON-based docs, graphics, 2D spreadsheets, 3D digital media graphics, hierarchical cloud storage systems, and more.</p><p>Crucially, we have implemented and applied these OT solutions to build numerous working co-editors for public demonstration or as co-editing products. Our implemented systems include pioneering Web-based plain-text co-editor REDUCE in the 1990s [4], desktop productivity tools like CoWord and CoPowerPoint, and digital design tools like CoMaya in the 2000s [5]. Moreover, we have developed a variety of Web-based rich-text co-editing products — <a href="https://codox.io/">Codox Apps</a> in recent years. It is important to highlight that all these co-editing systems and products have been built upon serverless or distributed OT solutions [4,5,7].</p><h3>Concluding Remarks</h3><p>In this article, I have addressed several common myths and misconceptions related to p2p, distributed, and commutative co-editing, providing corresponding facts, that are summarised in the following table.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*YQnAgSrfNxUckmqJfgqqnQ.png" /><figcaption><strong>Table 2. Myths and misconceptions contrasted with facts in p2p, distributed, and commutative co-editing.</strong></figcaption></figure><p>The recurring pattern of creating and spreading misconceptions, as highlighted in this article, severely undermines progress in the co-editing field and necessitates collective efforts for correction. We strongly believe that attaining a deep and accurate understanding of existing knowledge in co-editing is essential for dispelling these misconceptions. Equally crucial is our commitment to constructing arguments based on solid, comprehensive facts, avoiding misleading claims and unfounded assertions. Upholding these principles is essential for anchoring our progress firmly in the established foundation of the state-of-the-art.</p><p>In the ever-evolving landscape of co-editing, a continuous stream of new solution proposals come and go. To make a lasting impact, any proposed solution must demonstrate its value by either surpassing or complementing the capabilities of prior state-of-the-art solutions, without distorting reality or making false claims. Real-world applications serve as the litmus test for all solutions and the ultimate validation of co-editing research as a whole.</p><h3>References</h3><p>[1]. <a href="https://arxiv.org/abs/1905.01517">D. Sun, C. Sun, Agustina, W. Cai. “Real differences between OT and CRDT in building co-editing systems and real-world applications,” May 2, 2019.</a></p><p>[2] <a href="https://arxiv.org/abs/1905.01518">C. Sun, D. Sun, Agustina, W. Cai, B. Cho: “Real differences between OT and CRDT under a general transformation framework for consistency maintenance in co-editors, ” Proc. of the ACM on Human-Computer Interaction, 4(GROUP), Article 6, January 2020</a></p><p><a href="https://arxiv.org/abs/1905.01302">[3] D. Sun, C. Sun, Agustina, and W. Cai: “Real differences between OT and CRDT in correctness and complexity for consistency maintenance in co-editors,” Proc. of the ACM on Human-Computer Interaction, 4(CSCW1), May 2020.</a></p><p>[4] C. Sun, X. Jia, Y. Zhang, Y. Yang and D. Chen: “Achieving convergence, causality-preservation, and intention-preservation in real-time cooperative editing systems,” <em>ACM Transactions on Computer-Human Interaction, Vol.</em> 5, №1, pp.63–108, March 1998.</p><p>[5]. C. Sun, S. Xia, D. Sun, D. Chen, H.F. Shen and W. Cai: “ Transparent adaptation of single-user applications for multi-user real-time collaboration,” <em>ACM Transactions on Computer-Human Interaction</em>, Vol. 13, №4, pp. 531–582, December 2006.</p><p>[6] C. Sun, <a href="https://medium.com/codox/a-critical-examination-of-the-fugue-paper-in-relation-to-ot-157f6ccaed95">A Critical Examination of “the Fugue Paper” in Relation to OT</a>. Published on <em>medium</em> in August, 2023.</p><p>[7] C. Sun, “<a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">OTFAQ: Operational Transformation Frequently Asked Questions and Answers</a>.”</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=c4bfd1527ab5" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codox/debunking-myths-and-unveiling-facts-ot-vs-crdt-in-distributed-and-peer-to-peer-co-editing-c4bfd1527ab5">Debunking Myths and Unveiling Facts: OT vs. CRDT in Distributed and Peer-to-Peer Co-Editing</a> was originally published in <a href="https://medium.com/codox">Codox</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Dispelling Misconceptions in the Fugue Paper about GOT and OT]]></title>
            <link>https://medium.com/codox/dispelling-misconceptions-in-the-fugue-paper-about-got-and-ot-16e362609f6f?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/16e362609f6f</guid>
            <category><![CDATA[realtime-collaboration]]></category>
            <category><![CDATA[operationaltransformation]]></category>
            <category><![CDATA[crdt]]></category>
            <category><![CDATA[collaborative-editing]]></category>
            <category><![CDATA[sto]]></category>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Fri, 04 Aug 2023 01:29:39 GMT</pubDate>
            <atom:updated>2026-01-27T11:45:09.359Z</atom:updated>
            <content:encoded><![CDATA[<p>In the third installment of my ongoing series examining the Fugue paper’s claims about OT, I address its unfounded assertions concerning 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 illustrations and reasoning from my second post on Jupiter-OT. Therefore, this post focuses on addressing broader issues and misconceptions and unveiling the truth about the GOT algorithm and OT in general.</p><h4>1. Basic Facts of the GOT algorithm</h4><p>The GOT (Generic Operation Transformation) work was 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].</p><h4>GOT key features</h4><p>The GOT algorithm possesses the following key features:</p><ol><li>Functioning as a distributed OT control algorithm, without relying on a central transformation server.</li><li>Introducing the notion of operation context and context-based transformation conditions for OT correctness.</li><li>Solving the dOPT puzzle by ensuring the context-equivalence condition.</li><li>Achieving convergence without requiring the transformation functions to meet CP1 and CP2 transformation properties.</li><li>Incorporating a state-vector-based garbage collection scheme to remove operations from the history buffer that are no longer necessary for future transformation.</li></ol><h4>GOT can be integrated with any suitable transformation functions</h4><p>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&amp;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.</p><h4>GOT uses inclusion and exclusion transformation functions</h4><p>Differing from Jupiter-OT and the adOPTed algorithm, the GOT algorithm employs a pair of <em>Inclusion</em> and <em>Exclusion</em> transformation functions, which are obligated to meet a <em>reversibility</em> transformation property. This reversibility requirement increases the complexity of transformation functions and was eliminated in subsequent OT control algorithms such as NICE, TIBOT, COT, and POT, which exclusively utilize <em>Inclusion</em> transformation functions.</p><h4>GOT uses an internal undo-redo scheme for convergence</h4><p>Another special feature of the GOT algorithm is its use of an “<em>undo-redo</em>” scheme to achieve convergence, which helps to remove the necessity for transformation functions to ensure transformation properties CP1 and CP2 [3,4]. However, later research found the inefficiency and potential interface abnormalities to end-users caused by internal undo-redo-based concurrency control schemes (distinct from external UI undo features). As a result, subsequent OT control algorithms, including NICE, TIBOT 2.0, COT, and POT, were intentionally designed to avoid internal undo/redo while still being able to avoid CP2 without relying on transformation functions [3,4]. This highlights the continuous efforts to optimize OT solutions for both research and practical application purposes.</p><h4>Discovery of the FT puzzle</h4><p>The development of the GOT algorithm also brought to light the False-Tie (FT) puzzle, an instance of CP2 violation in text co-editing, which had influenced on subsequent development in co-editing. The FT puzzle and CP2 violation have been resolved through various approaches within the OT framework [4].</p><h4>2. Text-Interleaving is Prohibited in String-Wise Transformations</h4><p>In the Fugue paper, it was claimed that the “interleaving” problem “<em>has gone unnoticed for decades</em>.” 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, the matter of avoiding concurrent insertion interleaving had been explicitly addressed back in 1998 when designing string-wise transformation functions.</p><p>Section 9.1.3 “<em>Criteria for Verifying Intention-Preserved Effects</em>” 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:</p><blockquote>“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.”</blockquote><p>The statement that <em>“an Insert operation may never insert a string into the middle of another string inserted by an independent operation”</em> in the aforementioned quote clearly demonstrates that the string-wise transformation functions described in [2] have been intentionally designed to prohibit the occurrence of “interleaving” in concurrent insertions. This directly challenges the Fugue paper’s unfounded claim regarding the historical neglect of the “interleaving” problem.</p><h4>3. OT Control Algorithms are Independent of Text-Interleaving</h4><p>Text-interleaving is a special concern in text co-editing. It is a common misconception in some co-editing articles and discussions to attribute text co-editing issues to generic OT control algorithms.</p><p>In the Fugue paper, Jupiter-OT, adOPTed, and GOT are implicated as the cause of text-interleaving problems. However, even if the illustrations used to support such assertions were valid (which are not, as demonstrated in this series of posts), assigning the responsibility of text-editing specific issues to OT control algorithms is misguided and misleading. The correctness of an OT control algorithm is determined by its adherence to essential context-based conditions. These conditions are entirely unrelated to text-editing and, consequently, text-interleaving.</p><h4>4. Create OT Solutions by Flexible Combination</h4><h4>The OT modular structure</h4><p>A well-established approach to constructing a comprehensive OT solution involves the separation of the generic core OT control algorithms from application-specific transformation functions, with transformation properties and conditions in between specifying their interrelationships, as shown in Fig. 1.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/618/1*VR1EDRXggGdjqtl_T0e5Qw.jpeg" /><figcaption><strong>Fig. 1. The classic modular structure of an OT solution</strong></figcaption></figure><p>One significant advantage of this OT modular structure is the ability to design and validate OT components — 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.</p><h4>Independent development of OT components</h4><p>The last decade has witnessed significant expansion of OT into new co-editing domains through the creation of novel transformation functions tailed for diverse <a href="https://github.com/ottypes">data types</a>, such as <a href="https://github.com/ottypes/rich-text">QuillJS OT functions for rich-text co-editing</a>, <a href="https://github.com/ottypes/json0">JSON OT functions</a>, and more. Many of these transformation functions have been developed by open-source contributors and industry practitioners.</p><p>The success of this expansion can be attributed, in part, to the modular structure of OT solutions. The clear separation between OT components empowers co-editing application developers to focus on crafting transformation functions for a wide range of data types and applications, without the burden of dealing with control algorithm intricacies.</p><p>On the other hand, numerous OT control algorithms have been designed, and most of them are invented by academic researchers [4]. The detection and resolution of the dOPT puzzle led to the development of multiple OT control algorithms capable of ensuring the context-equivalence condition and the establishment of the theory of context-based conditions [2], which has become a cornerstone of OT correctness.</p><p>The landscape of OT has flourished with the publication of various OT control algorithms on one hand, and the availability of open-source transformation functions on the other. These developments offer abundant opportunities to create comprehensive OT solutions tailored to specific applications by flexibly combining suitable control algorithms and transformation functions.</p><h4>Support flexible co-editor communication topologies</h4><p>OT offers developers the freedom to choose between server-based or fully distributed communication topologies, allowing them to tailor solutions for their specific co-editing needs. Some control algorithms, like Jupiter-OT, NICE, and Google OT, are Sever-based OT (SOT) algorithms that use a central transformation server. Many other OT control algorithms, including adOPTed, GOT, SOCT, GOTO, COT, 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.</p><p>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 multiple factors, including the fact that the popular Google Docs utilizes an OT transformation server, a general lack of awareness and understanding of distributed OT algorithms, and the spread of misinformation.</p><p>Even among experienced industrial engineers and open-source practitioners who have developed practical OT-based co-editing products or designed useful transformation functions, there seems to be a lack of awareness or limited knowledge about the fact that OT can function perfectly without relying on a central server. This has led some to believe that their OT systems or functions were confined to operating with a central transformation server, thereby underestimating the true value of their work.</p><p>In fact, the client-server architecture adopted by most existing co-editing systems is primarily for supporting various aspects of co-editing, such as shared document storage, session management, message communications, and, optionally, for running server-side OT algorithms only if a server-based OT is used. While it is uncommon, if necessary, an existing SOT-based co-editing system can be transformed into a serverless DOT-based co-editing system by adopting a distributed OT control algorithm. This conversion does not necessitate modifying the existing transformation functions for the target application, nor does it require creating a new OT control algorithm, as there are numerous existing options readily available.</p><p>The notion that OT is unsuitable for peer-to-peer co-editing is simply false. For a deeper exploration of this topic, refer to Section 4 “Myths and Facts about Peer-to-Peer Co-Editing” in [3].</p><h4>The long-standing legacy of distributed OT and co-editing</h4><p>Gaining a profound and accurate understanding of the past is essential for charting a successful course into the future.</p><p>Historically, the first OT solution, dOPT (distributed OPerational Transformation), emerged in 1989 as a distributed optimistic concurrency control solution for plain-text co-editing. While server-based OT solutions like JUPITER-OT (1995), NICE (2002), and GOOGLE-OT (2008) followed later, most subsequent OT solutions, including dOPTed (1996), GOT (1997), SOCT (1997), GOTO (1998), TIBOT (2004), COT (2006), and POT (2016), have continued the distributed nature inherited from dOPT to function as distributed OT solutions. With a history of over 30 years in OT-based distributed co-editing, it is groundless and misleading to label OT as being server-dependent while claiming to invent a future of distributed co-editing.</p><p>Over the course of my 30-year experience in co-editing, I and my collaborators have designed and published a diverse array of OT solutions. These solutions include both distributed and server-based approaches, such as the generic control algorithms GOT (distributed), GOTO (distributed), NICE (server-based), COT (distributed), TIBOT (distributed), and POT (distributed), along with application-specific transformation functions catering to various data types, ranging from plain-text to rich-text, graphics, 2D spreadsheets, 3D digital media graphics, hierarchical cloud storage systems, and more.</p><p>Crucially, we have implemented and applied these OT solutions to build numerous publicly demonstrated co-editing systems. From first-hand experiences, we have learned that the primary challenges in co-editor implementation lie mostly in applying OT to address various co-editing issues and building comprehensive co-editing systems, rather than in just implementing OT core algorithms, which represent only a relatively small part of the overall co-editing system.</p><p>Our implemented systems include pioneering Web-based plain-text co-editor REDUCE in the 1990s, and desktop productivity tools like CoWord and CoPowerPoint, digital design tools like CoMaya in the early 2000s. Moreover, we have developed a variety of Web-based rich-text co-editing products — Codox Apps. It is worth highlighting that all these co-editing systems and products are built upon distributed OT solutions.</p><h4>5. Avoid Misusing OT Combination Power</h4><p>While the flexible combination of control algorithms and transformation has been instrumental in creating effective OT solutions, 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 lack of knowledge of OT fundamentals, but its repercussions are far-reaching. It perpetuates distorted views of OT, and hinders the overall progress of co-editing.</p><h4>Misguided combination of TTF and dOPT-like</h4><p>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 a dOPT-like algorithm. This combination of TTF with a dOPT-like algorithm resulted in a flawed solution that generated inconsistent and interleaving outcomes, which were then used in the Fugue paper to support the assertion of an interleaving issue in the adOPTed algorithm and TTF.</p><h4>Misconceptions surrounding TTF</h4><p>In fact, TTF has no connection to the char-interleaving issue either. However, other misconceptions surrounding TTF do exist. For example, in some articles and talks, TTF was portrayed as the sole correct OT solution, while simultaneously labeling OT control algorithms (such as adOPTed) as incorrect in comparison.</p><p>However, such a comparison is fundamentally incorrect 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.</p><h4>Distinguishing Correct vs Incorrect Combinations</h4><p>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.</p><p>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.</p><p>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.</p><p><a href="https://medium.com/codox/a-critical-examination-of-the-fugue-paper-in-relation-to-ot-157f6ccaed95">Part 1: A Critical Examination of “the Fugue Paper” in Relation to OT</a></p><p><a href="https://medium.com/codox/whats-wrong-with-the-fugue-paper-about-adopted-and-ot-9e74ffa0f828">Part 2: What’s wrong with the Fugue Paper about adOPTed and OT?</a></p><p><a href="https://medium.com/codox/unveiling-issues-with-the-fugue-paper-regarding-jupiter-ot-72565337b923">Part 3: Unveiling Issues with the Fugue Paper Regarding Jupiter-OT</a></p><h4>References</h4><p>[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.</p><p>[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, №1, pp.63–108, Mar., 1998.</p><p>[3] D. Sun, C. Sun, Agustina, W. Cai. “<a href="https://arxiv.org/abs/1905.01517">Real differences between OT and CRDT in building co-editing systems and real-world applications</a>,” May 2, 2019.</p><p>[4] C. Sun, “<a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">OTFAQ: Operational Transformation Frequently Asked Questions and Answers</a>.”</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=16e362609f6f" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codox/dispelling-misconceptions-in-the-fugue-paper-about-got-and-ot-16e362609f6f">Dispelling Misconceptions in the Fugue Paper about GOT and OT</a> was originally published in <a href="https://medium.com/codox">Codox</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[What’s wrong with the Fugue Paper about adOPTed and OT?]]></title>
            <link>https://medium.com/codox/whats-wrong-with-the-fugue-paper-about-adopted-and-ot-9e74ffa0f828?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/9e74ffa0f828</guid>
            <category><![CDATA[realtime-collaboration]]></category>
            <category><![CDATA[ot]]></category>
            <category><![CDATA[crdt]]></category>
            <category><![CDATA[operationaltransformation]]></category>
            <category><![CDATA[collaborative-editing]]></category>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Fri, 04 Aug 2023 01:27:57 GMT</pubDate>
            <atom:updated>2026-01-27T11:44:26.342Z</atom:updated>
            <content:encoded><![CDATA[<p>In this review, I will examine the <a href="https://arxiv.org/abs/2305.00583">Fugue paper’s</a> claims regarding the adOPTed algorithm. Through a detailed analysis, I will demonstrate that its description of the adOPTed algorithm is fundamentally flawed. Additionally, I will showcase that the adOPTed algorithm actually delivers consistent and non-interleaving outcomes, contrary to the paper’s claims. I will further discuss the origins of the dOPT-like flaw in the Fugue paper and emphasize the importance of grasping OT fundamentals to avoid the recurrence of similar errors.</p><p>Let’s examine the original text from the Fugue paper (A.1.1. page 18) that attempts to illustrate the “interleaving” problem in the adOPTed algorithm (published in [1]):</p><blockquote>“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 &lt; B and consider the execution at B:</blockquote><blockquote>1. B executes ins(1, x, B), so the document is x.</blockquote><blockquote>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 &amp; A&lt;B so a is inserted before x, yielding ax.</blockquote><blockquote>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 &gt; 1, so b is inserted after x, yielding axb.”</blockquote><p>It’s worth noting that the Fugue paper adopts a 1-based indexing convention for strings, rather than starting from 0. Throughout this series, I will also use the same indexing convention for easy comparison.</p><p>According to the above illustration, <em>x</em> is inserted inside the string <em>ab</em>, resulting in the final state <em>axb, </em>which seemingly indicates an interleaving problem in the adOPTed algorithm.</p><p>However, the above illustration in the Fugue paper is flawed.</p><h4>Fundamental Flaws in the Fugue Paper Illustration</h4><p>To illustrate the flaws intuitively, I present the co-editing scenario, with the details at replica B as depicted in the Fugue paper, in a time-space graph (Fig. 1).</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*jCF4oGFiQNOZnE6-TO7MgQ.jpeg" /><figcaption><strong>Fig. 1 Illustration of the adOPTed algorithm in the Fugue paper. In this illustration, the adOPTed algorithm is misrepresented and produces an interleaving result.</strong></figcaption></figure><p>In Step 3, according to the Fugue paper, when replica B receives <em>ins(2, b, A)</em>, it computes the transformation <strong><em>T(ins(2, b, A), ins(1, x, B)) = ins(3, b, A) </em>because <em>2 &gt; 1,</em></strong><em> </em>which is incorrect.</p><p>The correct transformation under the real adOPTed algorithm should be: <strong><em>T(ins(2, b, A), ins(2, x, B)) = ins(2, b, A)</em> because <em>2=2 &amp; A&lt;B</em></strong>. Therefore, <em>b</em> should be inserted before <em>x</em>, yielding <em>abx,</em> which is a <em>non-interleaved </em>outcome.</p><p>Where does the operation <strong><em>ins(2, x, B) </em></strong>come from? It comes from Step 2, in which the real adOPTed control algorithm should produce <strong><em>ins(2, x, B)</em></strong> using the transformation <strong><em>T(ins(1, x, B), ins(1, a, A))</em> because <em>1=1 &amp; A&lt;B</em></strong>. This important aspect was missing in the Fugue paper.</p><p>The correct illustration of replica B under the real adOPTed algorithm is shown in Fig. 2.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*q3wXGBckwpujcyo4FmgMdw.jpeg" /><figcaption><strong>Fig. 2 . Illustration of the real adOPTed algorithm’s working, which produces a non-interleaving result.</strong></figcaption></figure><h4>Exploring the Root of the Flaw: Illustration of Replica A</h4><p>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 Fugue paper) under the same scenario:</p><p>1. Replica A sequentially executes <em>ins(1, a, A) </em>and <em>ins(2, b, A),</em> resulting in the document being <em>ab</em>.</p><p>2. When A receives <em>ins(1, x, B)</em>, it computes two transformations in sequence:</p><ul><li><em>T(ins(1, x, B), ins(1, a, A)) = ins(2, x, B)</em> because <em>1=1 &amp; A&lt;B.</em></li><li><em>T(ins(2, x, B), ins(2, b, A)) = ins(3, x, B)</em> because <em>2=2 &amp; A&lt;B.</em></li></ul><p>As a result, <em>x</em> is inserted after <em>ab</em>, yielding <em>abx</em> at replica A. This result can be produced by both adOPTed algorithm and the dOPT algorithm.</p><p>By combining the illustration of replica A with replica B in both Fig. 1 and Fig. 2, we obtain the corresponding Fig. 3 and Fig. 4.</p><p>It is evident that the outcome <em>abx </em>at replica A differs from the result <em>axb </em>at replica B in Fig. 3, which means the result at replica B is not only <em>interleaving, </em>but worse, <em>inconsistent</em> as well.</p><p>In contrast, the result <em>abx</em> at replica A aligns with the corrected result <em>abx</em> at replica B in Fig. 4, which means both results are not only <em>non-interleaving</em> but also <em>consistent</em>, under the real adOPTed algorithm.</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*3j3RDklk8fPpdn-Y9aDtiQ.jpeg" /><figcaption><strong>Fig. 3. It turned out what is illustrated in the Fugue paper is not how the real adOPTed algorithm works, but the dOPT algorithm works.</strong></figcaption></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*9EwpqOU_Xb53Idf1ey_63Q.jpeg" /><figcaption><strong>Fig. 4 Illustration of how the adOPTed algorithm and other OT control algorithms solve the dOPT puzzle.</strong></figcaption></figure><h4>Unveiling the dOPT Puzzle: The Trap the Fugue Paper Falls Into</h4><p>The addition of the replica A illustration in Fig. 3 sheds light on the misrepresented behavior in the Fugue paper, which actually depicts the dOPT algorithm instead of the authentic adOPTed algorithm. The correct behavior of the adOPTed algorithm under the same scenario is demonstrated in Fig. 4.</p><p>In fact, the co-editing scenario in Fig. 3 represents an instance of the classic dOPT puzzle. This scenario involves three operations: <em>ins(1, a, A) </em>and <em>ins(2, b, A) </em>at replica A, causally related to each other, and <em>ins(1, x, B)</em> at replica B, concurrent with both operations at replica A. The concurrency relationships are as follows:</p><p><em>ins(1, a, A) → ins(2, b, A) || ins(1, x, B)</em></p><p>The resolution of the dOPT puzzle was the culmination of multiple years of independent research by multiple scholars in the 1990s. Once the puzzle was resolved, understanding why inconsistencies occurred in this scenario became straightforward for anyone with reasonable knowledge of OT and co-editing.</p><p>It is instructive to compare Fig. 3 with the generic and minimal dOPT puzzle illustration Fig. 5, which is taken from Q&amp;A 3.22 of OTFAQ [3 ].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*7uMBlgiN9fQFeh5LsAMMiA.png" /><figcaption><strong>Fig. 5. A generic illustration of the dOPT puzzle in OTFAQ.</strong></figcaption></figure><p>By comparing Fig. 3 and Fig. 5, I cannot help but wonder whether the dOPT-puzzle-like flaw, illustrated in Fig. 3, could have been avoided had the authors of the Fugue paper examined their co-editing scenario more comprehensively that included both replica A and replica B, and understood better the dOPT puzzle and its existing solutions [2].</p><h4>A Historical Perspective on Resolving the dOPT Puzzle</h4><p>It is regrettable that despite the resolution to the dOPT puzzle being available for approximately 30 years [2,3], its significance continues to be unknown or under-appreciated by some in the field of co-editing. The lack of awareness and appreciation regarding the insights and lessons gained from solving this puzzle have been significant contributing factors behind numerous misconceptions and flawed arguments surrounding OT.</p><p>Therefore, it is worth revisiting and emphasizing that the key idea to solving the dOPT puzzle is to ensure<em> context-equivalence</em> between the two input operations processed by the transformation function. Context-equivalence means that the operations are defined on the same document state. In the provided example, <em>ins(2, b, A)</em> (illustrated as <em>O2</em> in Fig. 1–4) is context-equivalent to <em>ins(2, x, B) </em>(illustrated as <em>O3&#39; </em>in Fig 4), whereas it is context-inequivalent to <em>ins(1, x, B)</em> (illustrated as <em>O3 </em>in Fig. 3). The effectiveness of transformation functions depends on accurately assessing positional relationships (e.g., left, right, or overlapping) between operations. This assessment requires defining operation positional (and other) parameters on the same state, which is the underlying reason for ensuring context-equivalence in OT.</p><p>As emphasized in Q&amp;A 3.16 of OTFAQ [3], ensuring context-equivalence is a <em>necessary</em> correctness requirement for all OT control algorithms. This means that every OT control algorithm must satisfy this condition to create a correct OT solution. Conversely, an OT control algorithm that cannot ensure context-equivalence will never produce a correct OT solution when combined with any transformation function. For instance, when the dOPT algorithm is combined with TTF functions, as illustrated in Fig. 3, the resulting OT solution is incorrect due to its inability to ensure context-equivalence.</p><p>The significance of context-based conditions extends beyond OT control algorithms and applies to transformation functions as well. Especially when operations handled by transformation functions involve more complex operations, such as <em>move, swap, </em>and others, adherence to context-based conditions becomes critical in ensuring correctness in these transformation functions.</p><h4>Summary</h4><p>In this review, I examined the Fugue paper’s claims concerning OT (adOPTed), provided evidence to prove the interleaving problem does not exist in adOPTed, and revealed the underlying misconceptions about OT. The valuable lesson learned from this review underscores the importance of understanding context-based conditions in OT solutions. By doing so, we can dispel misconceptions, avoid similar mistakes, and channel efforts towards more productive pursuits.</p><p><a href="https://medium.com/codox/unveiling-issues-with-the-fugue-paper-regarding-jupiter-ot-72565337b923">Next: Unveiling Issues with the Fugue Paper Regarding Jupiter-OT</a></p><p><a href="https://medium.com/codox/a-critical-examination-of-the-fugue-paper-in-relation-to-ot-157f6ccaed95">Previous: A Critical Examination of “the Fugue Paper” in Relation to OT</a></p><h4>References</h4><p>[1]. 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.</p><p>[2] C. Sun and C. Ellis. Operational transformation in real-time group editors: issues, algorithms, and achievements. ACM CSCW (1998), 59–68.</p><p>[3]. C. Sun, “<a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">OTFAQ: Operational Transformation Frequently Asked Questions and Answers</a>.”</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=9e74ffa0f828" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codox/whats-wrong-with-the-fugue-paper-about-adopted-and-ot-9e74ffa0f828">What’s wrong with the Fugue Paper about adOPTed and OT?</a> was originally published in <a href="https://medium.com/codox">Codox</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Unveiling Issues with the Fugue Paper Regarding Jupiter-OT]]></title>
            <link>https://medium.com/codox/unveiling-issues-with-the-fugue-paper-regarding-jupiter-ot-72565337b923?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/72565337b923</guid>
            <category><![CDATA[operationaltransformation]]></category>
            <category><![CDATA[crdt]]></category>
            <category><![CDATA[collaborative-editing]]></category>
            <category><![CDATA[sto]]></category>
            <category><![CDATA[realtime-collaboration]]></category>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Fri, 04 Aug 2023 01:24:57 GMT</pubDate>
            <atom:updated>2026-01-27T11:43:32.766Z</atom:updated>
            <content:encoded><![CDATA[<p>Continuing from my previous post titled “<a href="https://medium.com/codox/whats-wrong-with-the-fugue-paper-about-adopted-and-ot-9e74ffa0f828">What’s Wrong with the Fugue Paper about adOPTed and OT</a>?” I now present the second installment in this series, where I address the issues present in the Fugue paper regarding OT, with a specific focus on JUPITER-OT.</p><p>As with the previous review, let’s begin by examining the original text from the Fugue paper (A.1.3., page 19) that attempts to illustrate the “interleaving” problem in JUPITER-OT:</p><blockquote>“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.</blockquote><blockquote>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:</blockquote><blockquote>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.</blockquote><blockquote>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.</blockquote><blockquote>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.”</blockquote><p>The Fugue paper, specifically in the quoted text above, raises multiple issues regarding both OT in general and JUPITER-OT in particular. These issues have been grouped into three distinct sections for focused analysis.</p><h4>1. JUPITER-OT Capable of Supporting String-Wise Co-Editing</h4><p>I would like to refer to the following quoted statement: <em>“We arbitrarily chose to put server text first if both [i.e., server and client] try to insert at the same spot.”</em> 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:</p><blockquote>“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.”</blockquote><p>It is evident that JUPITER-OT supports a string-wise editing operation called “<em>replace</em>,” which involves a string-wise <em>delete</em> followed by a string-wise <em>insert</em>.</p><h4>Distinct characteristics of OT-based string-wise co-editing</h4><p>In the realm of OT, not only is string-wise co-editing more efficient than char-wise co-editing, but it also possesses distinct characteristics. One such feature is its ability to maintain the integrity of continuous text regions during insertion, ensuring that all texts within a region are inserted as a cohesive unit without becoming intertwined with concurrently inserted content.</p><p>Moreover, it is important to emphasize 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 creation of continuous strings during common editing actions that underscores the undesirability of text-interleaving and justify the efforts to avoid it in co-editing.</p><p>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 “<em>a</em>” and “<em>b</em>” (by client A) was represented as two separate char-wise operations: <em>insert(1, a)</em> and <em>insert(2, b)</em>, rather than a single string-wise <em>insert(1, ab)</em>, which could have occurred with JUPITER-OT or other OT solutions capable of supporting string-wise co-editing.</p><h4>String-wise co-editing eliminates interleaving</h4><p>With the string-wise operation “<em>ins(1, ab)</em>” capturing the continuous insertion of the characters “<em>a</em>” and “<em>b</em>”, 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):</p><p>Starting with an empty document, assume that client A initiates the insertion of two characters, “<em>a</em>” and “<em>b</em>”, sequentially, resulting in the operation “<em>ins(1, ab)</em>”; and concurrently client B inserts a single character “<em>x</em>”, leading to the operation “<em>ins(1, x)</em>”. Now examine the execution at the server:</p><p>1. Assume that client A’s <em>ins(1, ab)</em> is the first operation to reach the server, so the server simply applies it, resulting in the document “<em>ab</em>”.</p><p>2. Next, client B’s <em>ins(1, x)</em> reaches the server. Since <em>ins(1, ab)</em> was applied by the server, we have two concurrent insertions at the same position. According to the rule for such insertions, the server’s text, “<em>ab</em>” is placed first, and the client’s “<em>x</em>” is placed second. This means B’s operation is transformed into <em>ins(3, x),</em> and the server’s document now reads “<em>abx</em>” — a non-interleaving outcome.</p><p>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 “<em>xab</em>,” which remains non-interleaving.</p><p>In general, JUPITER-OT and other OT solutions that support string-wise co-editing, employ string-wise operations to handle continuous text region insertions. These solutions guarantee that concurrently inserted strings at the same position are sequentially placed in the merged document state, maintaining a consistent order without intermixing characters from different strings.</p><h4>2. JUPITER-OT Restricted to Supporting Char-Wise Co-Editing</h4><p>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.</p><h4>Combining JUPITER-OT with char-wise transformation functions</h4><p>Let’s explore the combination of the JUPITER-OT control algorithm with char-wise transformation functions described in Q&amp;A 2.15 (shown in Fig. 1) from OTFAQ [3].</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*4LRbDWMsUHjhd8IO2A_Gkg.jpeg" /><figcaption><strong>Fig. 1. Four char-wise transformation functions. The insert-tie breaking rule in Tii: when two operations insert at the same position, user ids are used to break the tie: if u1 &gt; u2, p1 remains unchanged; else p1 is incremented by 1 (right-shifted).</strong></figcaption></figure><p>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&amp;A 3.19 of the OTFAQ [3] titled “<em>How to create a correct OT system by combining existing control algorithms and transformation functions?</em>”</p><h4>Char-wise transformation capable of avoiding char-interleaving</h4><p>In Fig. 1, when two concurrent operations insert at the same position, the insert-tie-breaking rule is: <em>the operation with a smaller user id is right-shifted</em>.</p><p>Under similar conditions as described in the Fugue paper (assuming <em>A &gt; B</em>), the following sequence of events would unfold at the JUPITER server:</p><p>1. Assuming that <em>ins(1, a, A)</em> is the first operation to reach the server, it is straightforwardly applied, resulting in the document state: “<em>a</em>”.</p><p>2. Next, <em>ins(1, x, B)</em> reaches the server. Since <em>ins(1, x, B)</em> is <em>concurrent</em> and <em>context-equivalent</em> to <em>ins(1, a, A)</em>, the server applies the transformation <em>T(ins(1, x, B), ins(1, a, A))</em>, resulting in <em>ins(2, x, B)</em> due to the conditions <em>1 = 1</em> and <em>A &gt; B</em>. Executing <em>ins(2, x, B)</em> yields the document state: “<em>ax</em>”.</p><p>3. Finally, <em>ins(2, b, A)</em> arrives at the server. This operation is <em>concurrent</em> and <em>context-equivalent</em> to <em>ins(2, b, B)</em>. The server applies the transformation <em>T(ins(2, b, A), ins(2, X, B)),</em> resulting in <em>ins(2, b, A)</em> due to <em>2 = 2 </em>and <em>A &gt; B</em>. Executing <em>ins(2, b, A)</em> leads to the document state: “<em>abx</em>” (non-interleaving).</p><p>If the tie-breaking rule is reversed (<em>A &lt; B)</em>, another non-interleaving result would be obtained: “<em>xab</em>”.</p><p>As demonstrated in this simple example, JUPITER-OT has the ability to consistently generate non-interleaving outcomes, even when utilized alongside transformation functions that exclusively operate at the character level.</p><h4>A shared characteristic among OT solutions</h4><p>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 (Fig. 2 and Fig. 4) using the adOPTed control algorithm in my previous post. 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 many generic OT control algorithms [2,3].</p><p>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.</p><h4>3. State-of-the-Art and the Future of Co-Editing</h4><p>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.</p><h4>Steering towards new and genuine challenges</h4><p>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.</p><p>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 toward addressing these challenges and moving the field forward.</p><h4>Choosing the path: forward or backward?</h4><p>Given the current state-of-art of co-editing and emerging challenges ahead of us, it is puzzling to witness a regressive resurgence of works centered around plain-text char-wise co-editing. These works often delve into seemingly contrived topics, such as the “<em>backward interleaving</em>” explored in the Fugue paper.</p><p>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 “<em>abc</em>” is created in reverse order, with ‘<em>c</em>’ first, ‘<em>b</em>’ second, and ‘<em>a</em>’ last. Now, suppose another user concurrently inserts the character “<em>x</em>” at the same position as “<em>a</em>.” Will “<em>x</em>” be injected in the middle of this backward-created string “<em>abc</em>” in the final merged result? That’s the question investigated under the notion of “<em>backward interleaving</em>”.</p><p>Similarly, discussions revolving around “<em>multi-user-relay interleaving</em>”, also known as “<em>multi-replica interleaving</em>” 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 “<em>a</em>”, followed by user B typing “<em>b</em>” to form the sequence “<em>ab</em>”, and finally, user C adds the character “<em>c</em>” to complete the string as “<em>abc</em>”. Now, the question arises in the context of “multi-user-relay” interleaving: is there a possibility that this string “<em>abc</em>” becomes interleaved with another character “<em>x</em>” concurrently inserted by yet another user?</p><p>Further discussions regarding the combination of “<em>multi-user-relay interleaving</em>” and “<em>backward interleaving</em>” become increasingly implausible. This is demonstrated by examining the possibility of text-interleaving under a hypothetical scenario: user C initiates the process by inputting “<em>c</em>” and relaying it to user B, who prefixes “<em>b</em>” to create the sub-string “<em>bc</em>” before passing it on to user A. Subsequently, user A contributes the character “<em>a</em>,” resulting in the formation of “<em>abc</em>.” Meanwhile, user D, who is unaware of the existence of “<em>abc,</em>” independently types the character <em>“x</em>” at the same position as “<em>a</em>.” This raises the question: Can character “<em>x</em>” become entwined in the middle of the string “<em>abc</em>”, created in such a “<em>multi-user-backward-relay</em>” fashion?</p><p>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?</p><h4>Embracing the future: advancing forward</h4><p>It is important to critically evaluate the relevance and significance of topics, whether they pertain to research or practical applications, within the current and broader context of co-editing. Such evaluations are essential in fostering valuable advancements and innovations, both in research endeavors and in the development of practical solutions. By conducting these assessments, we can ensure that our efforts are directed toward addressing genuine challenges and opportunities in the co-editing field, thus propelling it forward into the future.</p><p><a href="https://medium.com/codox/dispelling-misconceptions-in-the-fugue-paper-about-got-and-ot-16e362609f6f">Next: Dispelling Misconceptions in the Fugue Paper about GOT and OT</a></p><p><a href="https://medium.com/codox/whats-wrong-with-the-fugue-paper-about-adopted-and-ot-9e74ffa0f828">Previous: What’s wrong with the Fugue Paper about adOPTed and OT?</a></p><h4>References:</h4><p>[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.</p><p>[2] 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.</p><p>[3]. C. Sun, “<a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">OTFAQ: Operational Transformation Frequently Asked Questions and Answers</a>.”</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=72565337b923" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codox/unveiling-issues-with-the-fugue-paper-regarding-jupiter-ot-72565337b923">Unveiling Issues with the Fugue Paper Regarding Jupiter-OT</a> was originally published in <a href="https://medium.com/codox">Codox</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[A Critical Examination of “the Fugue Paper” in Relation to OT]]></title>
            <link>https://medium.com/codox/a-critical-examination-of-the-fugue-paper-in-relation-to-ot-157f6ccaed95?source=rss-e237dc30292a------2</link>
            <guid isPermaLink="false">https://medium.com/p/157f6ccaed95</guid>
            <category><![CDATA[sto]]></category>
            <category><![CDATA[algorithms]]></category>
            <category><![CDATA[collaborative-editing]]></category>
            <category><![CDATA[real-time-collaboration]]></category>
            <category><![CDATA[crdt]]></category>
            <dc:creator><![CDATA[Dr. Chengzheng Sun]]></dc:creator>
            <pubDate>Thu, 03 Aug 2023 02:36:08 GMT</pubDate>
            <atom:updated>2026-01-27T11:42:38.557Z</atom:updated>
            <content:encoded><![CDATA[<p>Welcome to a series of critical reviews of the paper titled “<a href="https://arxiv.org/abs/2305.00583">The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing</a>,” referred to as “the Fugue paper” in this series.</p><p>The introductory paragraph of the Fugue paper’s abstract states:</p><blockquote>“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.”</blockquote><h4><strong>Is “interleaving” a new issue in CRDT?</strong></h4><p>The problem of text interleaving in certain CRDT solutions, like Logoot, is neither recent nor overlooked. We thoroughly examined and documented such interleaving cases in [5] back in 2018. For those interested, a detailed visual representation of how and why interleaving occurs in CRDT can be found in Figure 2 of Section 4.4 (“<em>Hidden Correctness Issues in Logoot</em>”). An earlier version of this paper can be accessed at this <a href="https://arxiv.org/abs/1810.02137">URL</a>.</p><h4><strong>Is “interleaving” an issue in OT?</strong></h4><p>What sets the Fugue paper apart is its identification of the interleaving problem in several early Operational Transformation (OT) solutions, namely JUPITER OT [1] (published in 1995), adOPTed control algorithm [2] (published in 1996), GOT control algorithm [3] (published in 1997), and TTF functions (published in 2006).</p><p>The Fugue paper uses illustrations to describe instances where the interleaving problem manifests in these OT solutions. From there, the authors attempt to generalize the issue through broad statements, such as “<em>… existing algorithms for replicated lists, which are widely used in collaborative text editors…</em>” and “<em>… all text collaboration algorithms have an interleaving problem.</em>” These statements imply that interleaving is a prevalent issue across all OT and co-editing solutions.</p><h4>Are the sweeping claims in the Fugue paper justifiable?</h4><p>However, even if we were to accept the reported interleaving problem in the OT solutions mentioned above as real (which is not the case, as demonstrated in this series of reviews), it would be dubious to make sweeping claims such as “<em>all text collaboration algorithms have an interleaving problem</em>”. This is due to the existence of numerous other co-editing solutions not covered in the Fugue paper, including GOTO (ACM CSCW1998), NICE (ACM CSCW2002), TIBOT (IEEE ICPADS2004), COT (ACM CSCW2006), GOOGLE WAVE and Docs OT (2010), and POT (IEEE TPDS2016), to name just a subset of the vast co-editing landscape. It is also important to acknowledge that these examples do not encompass a considerable number of industry and open-source OT solutions as well.</p><h4>Main motivations</h4><p>Having been involved in co-editing since the 1990s, I have extensive familiarity with various OT solutions, including those mentioned in the Fugue paper. However, I must admit that I was previously unaware of the interleaving problem in any of these solutions. Naturally, the report in 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 claims in the Fugue paper.</p><h4>My findings</h4><p>After a thorough review, I find the issues and claims made in the paper regarding the various co-editing solutions to be demonstrably flawed, and the paper contained numerous misconceptions about OT and co-editing in general. I will share these findings through a series of reviews, each focusing on a specific solution and addressing general OT issues as they relate to the Fugue paper. The primary aim of this series is to disseminate accurate information about co-editing solutions and to provide insights to those who rely on this knowledge.</p><p>Following valuable feedback on earlier versions (posted at <a href="https://news.ycombinator.com/item?id=36208585">Hacker News</a>), I revised and extended these reviews. The revised review titles and abstracts are as follows:</p><h4>1. <a href="https://medium.com/codox/whats-wrong-with-the-fugue-paper-about-adopted-and-ot-9e74ffa0f828">What’s Wrong with the Fugue Paper about adOPTed and OT?</a></h4><p>In this review, I will delve into the Fugue paper’s claims regarding the adOPTed algorithm. Through meticulous analysis, I will reveal fundamental flaws in the Fugue paper’s description of the adOPTed algorithm and present compelling evidence showcasing the consistent and non-interleaving outcomes delivered by the adOPTed algorithm. I delve into the origins of the dOPT-like flaw in the Fugue paper and emphasize the significance of grasping OT fundamentals to avoid the recurrence of similar errors in future work.</p><h4>2.<a href="https://medium.com/codox/unveiling-issues-with-the-fugue-paper-regarding-jupiter-ot-72565337b923"> Unveiling Issues with the Fugue Paper Regarding Jupiter-OT</a></h4><p>In this second review, I will provide a comprehensive explanation of why Jupiter-OT consistently produces non-interleaving outcomes, regardless of whether it is employed with string-wise or char-wise transformation functions. This review will refute unfounded claims about Jupiter-OT’s “char-interleaving” problem, while questioning the relevance and value of discussing concepts like “<em>multi-user-backward-relay-interleaving</em>.”</p><h4>3. <a href="https://medium.com/codox/dispelling-misconceptions-in-the-fugue-paper-about-got-and-ot-16e362609f6f">Dispelling Misconceptions in the Fugue Paper about GOT and OT</a></h4><p>In this third review, I will focus on debunking the Fugue paper’s unfounded assertions about the GOT algorithm. By employing similar reasoning to the previous reviews, I will dispel any alleged “char-interleaving” problem in GOT. This review will also address broader issues, aiming to dispel misconceptions about OT in general and provide a more accurate understanding of co-editing solutions.</p><p>Through these reviews, I hope to contribute to a better understanding of co-editing technologies and promote informed discussions within the research and practitioner communities, facilitating meaningful progress in the field of collaborative editing.</p><h4>References:</h4><p>[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.</p><p>[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.</p><p>[3]. 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, №1, pp.63–108, Mar., 1998.</p><p>[4] 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.</p><p>[5]. D. Sun, C. Sun, Agustina Ng, and W. Cai: “ Real differences between OT and CRDT in correctness and complexity for consistency maintenance in co-editors,” Proc. of the ACM on Human-Computer Interaction, 4(CSCW1), May 2020. doi:10.1145/3392825. Also available at this <a href="https://arxiv.org/abs/1905.01302">URL</a>.</p><p>[6]. C. Sun, “<a href="https://www3.ntu.edu.sg/computing/staff/czsun/projects/otfaq/">OTFAQ: Operational Transformation Frequently Asked Questions and Answers</a>.”</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=157f6ccaed95" width="1" height="1" alt=""><hr><p><a href="https://medium.com/codox/a-critical-examination-of-the-fugue-paper-in-relation-to-ot-157f6ccaed95">A Critical Examination of “the Fugue Paper” in Relation to OT</a> was originally published in <a href="https://medium.com/codox">Codox</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>