Reference. Peritext: A CRDT for Collaborative Rich Text Editing
Conflict-Free Replicated Data Types (CRDTs) support decentralized collaborative editing of shared data, enabling peer-to-peer sharing and flexible branching and merging workflows. While there is extensive work on CRDTs for plain text, much less is known about CRDTs for rich text with formatting. No algorithms have been published, and existing open-source implementations do not always preserve user intent. In this paper, we describe a model of intent preservation in rich text editing, developed through a series of concurrent editing scenarios. We then describe Peritext, a CRDT algorithm for rich text that satisfies the criteria of our model. The key idea is to store formatting spans alongside the plaintext character sequence, linked to a stable identifier for the first and last character of each span, and then to derive the final formatted text from these spans in a deterministic way that ensures concurrent operations commute. We have prototyped our algorithm in TypeScript, validated it using randomized property-based testing, and integrated it with an editor UI. We also prove that our algorithm ensures convergence, and demonstrate its causality preservation and intention preservation properties.
Cite
Cited by (1)
Grove: A Bidirectionally Typed Collaborative Structure Editor Calculus adams-2025-grove
Version control systems typically rely on a patch language , heuristic patch synthesis algorithms like diff , and three-way merge algorithms . Standard patch languages and merge algorithms often fail to identify conflicts correctly when there are multiple edits to one line of code or code is relocated. This paper introduces Grove, a collaborative structure editor calculus that eliminates patch synthesis and three-way merge algorithms entirely. Instead, patches are derived directly from the log of the developer’s edit actions and all edits commute, i.e. the repository state forms a commutative replicated data type (CmRDT). To handle conflicts that can arise due to code relocation, the core datatype in Grove is a labeled directed multi-graph with uniquely identified vertices and edges. All edits amount to edge insertion and deletion, with deletion being permanent. To support tree-based editing, we define a decomposition from graphs into groves , which are a set of syntax trees with conflicts–including local, relocation, and unicyclic relocation conflicts–represented explicitly using holes and references between trees. Finally, we define a type error localization system for groves that enjoys a totality property, i.e. all editor states in Grove are statically meaningful, so developers can use standard editor services while working to resolve these explicitly represented conflicts. The static semantics is defined as a bidirectional marking system in line with recent work, with gradual typing employed to handle situations where errors and conflicts prevent type determination. We then layer on a unification-based type inference system to opportunistically fill type holes and fail gracefully when no solution exists. We mechanize the metatheory of Grove using the Agda theorem prover. We implement these ideas as the Grove Workbench , which generates the necessary data structures and algorithms in OCaml given a syntax tree specification.
Cites 48 works (0 here)
External (48)
- Papyrus: rich text CRDT from 2012 (2021)
- Peritext prototype implementation (2021)
- Local-first software: you own your data, in spite of the cloud (2019)
- Lessons learned from creating a rich-text editor with real-time collaboration (2018)
- Conflict-free replicated data types: an overview (2018)
- Pure operation-based replicated data types (2017)
- Enhancing rich content wikis with real-time collaboration (2017)
- Exhaustive Search and Resolution of Puzzles in OT Systems Supporting String-Wise Operations (2017)
- Verifying strong eventual consistency in distributed systems (2017)
- High Responsiveness for Group Editing CRDTs (2016)
- A Conflict-Free Replicated JSON Datatype (2016)
- Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types (2016)
- Rich text type for Yjs (2016)
- wiki-transformation.md (2016)
- Collaborative editing in ProseMirror (2015)
- ProseMirror: a toolkit for building rich-text editors on the web (2015)
- TP1-valid transformation functions for operations on ordered n-ary trees (2015)
- Supporting adaptable granularity of changes for massive-scale collaborative editing (2013)
- LSEQ: an adaptive structure for sequences in distributed collaborative editing (2013)
- Introduction to Reliable and Secure Distributed Programming (2011)
- Replicated abstract data types: Building blocks for collaborative applications (2011)
- Conflict-Free Replicated Data Types (2011)
- Deep hypertext with embedded revision control implemented in regular expressions (2010)
- Scalable XML collaborative editing with undo (2010)
- What's different about the new Google Docs: making collaboration fast (2010)
- A Commutative Replicated Data Type for Cooperative Editing (2009)
- Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks (2009)
- Multi-level Editing of Hierarchical Documents (2008)
- A performance study of group editing algorithms (2006)
- Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems (2006)
- Data consistency for P2P collaborative editing (2006)
- Transparent adaptation of single-user applications for multi-user real-time collaboration (2006)
- Operational Transformation for Collaborative Word Processing (2004)
- Leveraging single-user applications for multi-user collaboration: the coword approach (2004)
- Customizable Collaborative Editor Relying on treeOPT Algorithm (2003)
- Generalizing operational transformation to the standard general markup language (2002)
- Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems (1998)
- High-latency, low-bandwidth windowing in the Jupiter collaboration system (1995)
- Design Issues and Model for a Distributed Multi-User Editor (1994)
- Duplex: A Distributed Collaborative Editing Environment in Large Scale (1994)
- Lightweight causal and atomic group multicast (1991)
- Concurrency control in groupware systems (1989)
- Replicated document management in a group communication system (1988)
- A Majority consensus approach to concurrency control for multiple copy databases (1979)
- Time, clocks, and the ordering of events in a distributed system (1978)
- Convergence Examples: Froala
- Convergence developer guide: real time models
- Convergence JavaScript client: transformation functions