A text cursor is not a location in the distributed-systems sense.

On your machine, “insert after character 6” is perfectly meaningful. Across two offline replicas, it is a rumor. By the time the operation arrives elsewhere, character 6 may have moved, split, disappeared, or become surrounded by someone else’s work.

Collaborative text editing therefore has to answer a stranger question:

what is the durable address between these two characters?

That address has to survive network delay. It has to be generated locally, before asking a server for permission. It has to make independently edited copies converge. And it has to produce text that a human can still read.

Those are different requirements. Convergence says every replica ends in the same state. It does not say the state is a good merge.

Dense Positions Feel Natural

One family of sequence CRDTs gives every inserted character an identifier drawn from a dense ordered space. If two visible characters have positions 0.49 and 0.64, an inserted character can take something in between. The document order is then just identifier order.

That is the Logoot/LSEQ flavor of solution.12 The cursor becomes an interval. Inserting text means manufacturing new addresses inside that interval. Since replicas use the same total order, shuffled network delivery can still converge.

The catch is that “between” is not free. If users keep inserting near the same boundary, identifiers need more digits. If two users concurrently type passages at the same place, a naive allocation strategy can give both passages matching address ladders. A deterministic tie-breaker then does exactly what it was asked to do: sort the characters by address.

The result can be character-level interleaving.

Convergence Is Too Weak

Kleppmann, Gomes, Mulligan, and Beresford made this failure mode explicit in their work on interleaving anomalies.3 Two users concurrently insert readable passages at the same cursor. A convergent algorithm may merge them into a single unreadable braid.

This is not a mere aesthetic complaint. A collaborative editor is not a set. The relative order of characters carries user intent. If Alice typed a phrase, most of the time the merged document should preserve that phrase as a phrase, even if Bob typed another phrase at the same place.

The specification work by Attiya, Burckhardt, Gotsman, Morrison, Yang, and Zawirski is useful here because it separates the abstract list behavior from the implementation trick.4 It also shows why metadata is not accidental. For a large class of list protocols, correctness forces metadata overhead that grows at least linearly with the number of deleted elements. Tombstones and causal addresses are not ugly leftovers. They are evidence.

Lab: Two People Type At The Same Cursor

The lab below stages a deliberately small race. Several replicas type short phrases at the same initial cursor while offline. Then their operations arrive in a shuffled order.

It compares two simplified merge disciplines:

Fractional position IDs. Each local keystroke allocates an ordered address between the previous local character and the right boundary. The final document is sorted by (address, replica, local sequence). This is a toy stand-in for the position-identifier family, not an implementation of Logoot or LSEQ.

Left-origin list. Each inserted character stores the character it followed at creation time. The final document is a deterministic traversal of that left-origin forest. This is an RGA-style toy: good enough to expose the causality shape, not a production editor.

Alice Bob Chandra Dana

With the default settings, the position-ID row reads something like a braid: Alice’s first letter, Bob’s first letter, Alice’s second letter, Bob’s second letter, and so on. The addresses are doing their job. They converge. They are also preserving the wrong local structure.

The left-origin row does a different kind of bookkeeping. Alice’s second character says “I came after Alice’s first character.” Bob’s second character says the same about Bob’s first. When both first characters are concurrent children of the same old cursor, a deterministic tie-breaker chooses which run comes first. But once a run starts, its descendants stay attached.

The cost shows up in the audit. Some shuffled deliveries are causally early: A:4 may arrive before A:3. The toy left-origin engine buffers those messages until their parent is present. Real systems hide that machinery behind causal delivery, operation buffers, sync protocols, tombstones, or compacted history.

The Address Is A Claim About Intent

There is no universally correct merge of concurrent prose. If Alice writes blue and Bob writes green at the same place, maybe the right document is bluegreen. Maybe it is greenblue. Maybe it should expose a conflict. But it is rarely bglrueeen.

This is why newer work talks about non-interleaving as a correctness property, not just a UI preference. Weidner and Kleppmann’s Fugue work defines maximal non-interleaving and gives CRDT algorithms designed around it.5 The interesting part is not that a clever tie-breaker exists. It is that the correctness property had to name a human-visible failure mode that ordinary strong eventual consistency did not rule out.

There is a second pressure: storage. Text editing histories are full of deletes, undoes, replaced paragraphs, and formatting moves. If the algorithm needs old positions to interpret future operations, deleting visible text does not necessarily delete its role in the address system. Attiya and coauthors’ lower bound is the hard version of that lesson: in broad peer-to-peer list protocols, some metadata growth is inherent.4

So a collaborative editor has three ledgers, not one:

  1. the visible document,
  2. the causal evidence needed to merge future operations,
  3. the human intent properties the merge is supposed to preserve.

Optimizing only the first ledger is how a text editor becomes a sorting algorithm.

Why This Still Feels Current

Local-first software made this problem feel fresh again. If the user should be able to work offline, own their files, sync peer-to-peer, and later merge without asking a central server to serialize every keystroke, the document format itself has to carry enough history.

That does not mean old sequence CRDTs are the final answer. Eg-walker, by Joseph Gentle and Martin Kleppmann, is a recent hybrid direction: keep editing events in a compact form, walk the event graph when merging, and aim for much lower steady-state memory and load time than conventional CRDT storage while retaining peer-to-peer applicability.6

The design space is not “OT versus CRDT” as team jerseys. It is:

what history is stored, when is it replayed, and which merge anomalies are ruled out?

The tiny lab above is deliberately unfair to production algorithms. It uses a pathological same-cursor race and a simple address allocator. But that unfairness is useful. It isolates the thing a good editor must prevent.

A cursor offset is where your hand is.

A collaborative text address is what your future replicas can still prove.

  1. Stephane Weiss, Pascal Urso, and Pascal Molli, “Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks”, ICDCS 2009. DOI: 10.1109/ICDCS.2009.75. The CRDT paper index lists it under text-editing sequence CRDTs: crdt.tech papers. ↩

  2. Brice Nedelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils, “LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing”, DocEng 2013. ACM DOI. A public slide/PDF version summarizes the allocation strategy and identifier-size experiments: ConcoRDanT PDF. ↩

  3. Martin Kleppmann, Victor B. F. Gomes, Dominic P. Mulligan, and Alastair R. Beresford, “Interleaving anomalies in collaborative text editors”, PaPoC 2019. PDF, ACM DOI. ↩

  4. Hagit Attiya, Sebastian Burckhardt, Alexey Gotsman, Adam Morrison, Hongseok Yang, and Marek Zawirski, “Specification and space complexity of collaborative text editing”, Theoretical Computer Science 855:141-160, 2021; earlier PODC 2016 version. Microsoft Research, PDF. ↩ ↩2

  5. Matthew Weidner and Martin Kleppmann, “The Art of the Fugue: Minimizing Interleaving in Collaborative Text Editing”, submitted 2023, revised 2025, IEEE Transactions on Parallel and Distributed Systems 36(11):2425-2437. arXiv, DOI. ↩

  6. Joseph Gentle and Martin Kleppmann, “Collaborative Text Editing with Eg-walker: Better, Faster, Smaller”, accepted at EuroSys 2025. arXiv, ACM DOI, artifact repository. ↩