research-article

Open access

Peritext: A CRDT for Collaborative Rich Text Editing

Authors:

Martin Kleppmann, and

Peter van HardenbergAuthors Info & Claims

Proceedings of the ACM on Human-Computer Interaction, Volume 6, Issue CSCW2

Article No.: 531, Pages 1 - 36

https://doi.org/10.1145/3555644

Published: 11 November 2022 Publication History

Abstract

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.

References

[1]

Luc Andre, Stephane Martin, Gerald Oster, and Claudia-Lavinia Ignat. 2013. Supporting Adaptable Granularity of Changes for Massive-scale Collaborative Editing. In Proceedings of the 9th IEEE International Conference on Collaborative Computing: Networking, Applications and Worksharing. ICST, Austin, United States. https://doi.org/10.4108/icst.collaboratecom.2013.254123

[2]

Carlos Baquero, Paulo Sérgio Almeida, and Ali Shoker. 2017. Pure Operation-Based Replicated Data Types. arXiv:1710.04469 https://arxiv.org/abs/1710.04469

[3]

Kenneth P Birman, André Schiper, and Pat Stephenson. 1991. Lightweight causal and atomic group multicast. ACM Transactions on Computer Systems 9, 3 (Aug. 1991), 272--314. https://doi.org/10.1145/128738.128742

Digital Library

[4]

Loïck Briot, Pascal Urso, and Marc Shapiro. 2016. High Responsiveness for Group Editing CRDTs. In Proceedings of the 19th International Conference on Supporting Group Work. ACM, Sanibel Island Florida USA, 51--60. https://doi.org/10.1145/2957276.2957300

Digital Library

[5]

Christian Cachin, Rachid Guerraoui, and Luís Rodrigues. 2011. Introduction to Reliable and Secure Distributed Programming (second ed.). Springer. https://doi.org/10.1007/978--3--642--15260--3

[6]

Jason Chen, Zihua Li, and David Greenspan. [n.d.]. Quill Delta. https://github.com/quilljs/delta

[7]

Szymon Cofalik and Anna Tomanek. 2018. Lessons learned from creating a rich-text editor with real-time collaboration. https://ckeditor.com/blog/Lessons-learned-from-creating-a-rich-text-editor-with-real-time-collaboration/

[8]

Convergence Labs, Inc. [n.d.]. Convergence Developer Guide: Real Time Models. https://docs.convergence.io/guide/models/real-time-models/

[9]

Convergence Labs, Inc. [n.d.]. Convergence Examples: Froala. https://examples.convergence.io/examples/froala/

[10]

Aguido Horatio Davis, Chengzheng Sun, and Junwei Lu. 2002. Generalizing Operational Transformation to the Standard General Markup Language. In ACM Conference on Computer Supported Cooperative Work (CSCW 2002). ACM, 58--67. https://doi.org/10.1145/587078.587088

Digital Library

[11]

John Day-Richter. 2010. What's different about the new Google Docs: Making collaboration fast. https://drive.googleblog.com/2010/09/whats-different-about-new-google-docs.html

[12]

Clarence A Ellis and Simon J Gibbs. 1989. Concurrency control in groupware systems. In ACM International Conference on Management of Data (SIGMOD 1989). ACM, 399--407. https://doi.org/10.1145/67544.66963

Digital Library

[13]

Victor B. F. Gomes, Martin Kleppmann, Dominic P. Mulligan, and Alastair R. Beresford. 2017. Verifying Strong Eventual Consistency in Distributed Systems. Proceedings of the ACM on Programming Languages 1, OOPSLA, Article 109 (Oct. 2017). https://doi.org/10.1145/3133933

Digital Library

[14]

Victor Grishchenko. 2010. Deep hypertext with embedded revision control implemented in regular expressions. In 6th International Symposium on Wikis and Open Collaboration (WikiSym 2010). ACM. https://doi.org/10.1145/1832772.1832777

Digital Library

[15]

Victor Grishchenko. 2021. Papyrus: rich text CRDT from 2012. https://github.com/gritzko/citrea-model/blob/master/ story.md

[16]

Raman Gupta. 2015. Ritzy Editor. https://github.com/ritzyed/ritzy

[17]

Marijn Haverbeke. 2015. Collaborative Editing in ProseMirror. https://marijnhaverbeke.nl/blog/collaborative-editing.html

[18]

Marijn Haverbeke. 2015. ProseMirror: A toolkit for building rich-text editors on the web. https://prosemirror.net/

[19]

Claudia-Lavinia Ignat, Luc André, and Gérald Oster. 2017. Enhancing rich content wikis with real-time collaboration. Concurrency and Computation: Practice and Experience 33, 8 (March 2017). https://doi.org/10.1002/cpe.4110

[20]

Claudia-Lavinia Ignat and Moira C Norrie. 2003. Customizable Collaborative Editor Relying on treeOPT Algorithm. In 8th European Conference on Computer-Supported Cooperative Work (ECSCW 2003). Springer, 315--334. https://doi.org/10.1007/978--94-010-0068-0_17

[21]

Claudia-Lavinia Ignat and Moira C. Norrie. 2008. Multi-level Editing of Hierarchical Documents. Computer Supported Cooperative Work 17 (2008), 423-468. https://doi.org/10.1007/s10606-007--9071--2

[22]

Kevin Jahns. 2016. Rich Text type for Yjs. https://github.com/y-js/y-richtext

[23]

Tim Jungnickel and Tobias Herb. 2015. TP1-valid Transformation Functions for Operations on ordered n-ary Trees. https://arxiv.org/abs/1512.05949

[24]

Leonard Kawell Jr., Steven Beckhardt, Timothy Halvorsen, Raymond Ozzie, and Irene Greif. 1988. Replicated document management in a group communication system. In ACM Conference on Computer-Supported Cooperative Work (CSCW). ACM. https://doi.org/10.1145/62266.1024798

Digital Library

[25]

Martin Kleppmann. 2022. Automerge. https://github.com/automerge/automerge

[26]

Martin Kleppmann and Alastair R Beresford. 2017. A Conflict-Free Replicated JSON Datatype. IEEE Transactions on Parallel and Distributed Systems 28, 10 (April 2017), 2733--2746. https://doi.org/10.1109/tpds.2017.2697382

Digital Library

[27]

Martin Kleppmann, Adam Wiggins, Peter van Hardenberg, and Mark McGranaghan. 2019. Local-First Software: You Own Your Data, in Spite of the Cloud. In Proceedings of the 2019 ACM SIGPLAN International Symposium on New Ideas, New Paradigms, and Reflections on Programming and Software - Onward! 2019. ACM Press, Athens, Greece, 154--178. https://doi.org/10.1145/3359591.3359737

Digital Library

[28]

Michael Koch. 1994. Design Issues and Model for a Distributed Multi-User Editor. Computer Supported Cooperative Work 3 (Sept. 1994), 359--378. https://doi.org/10.1007/BF00750746

Digital Library

[29]

Leslie Lamport. 1978. Time, clocks, and the ordering of events in a distributed system. Commun. ACM 21, 7 (July 1978), 558--565. https://doi.org/10.1145/359545.359563

Digital Library

[30]

Du Li and Rui Li. 2006. A performance study of group editing algorithms. In 12th International Conference on Parallel and Distributed Systems (ICPADS 2006). IEEE. https://doi.org/10.1109/icpads.2006.18

Digital Library

[31]

Geoffrey Litt, Sarah Lim, Martin Kleppmann, and Peter van Hardenberg. 2021. Peritext prototype implementation. Available at https://github.com/inkandswitch/peritext. https://doi.org/10.17863/CAM.87326

[32]

Michael MacFadden. [n.d.]. Convergence JavaScript Client: Transformation Functions. https://github.com/convergencelabs/convergence-client-javascript/tree/master/src/main/model/ot/xform

[33]

Stéphane Martin, Pascal Urso, and Stéphane Weiss. 2010. Scalable XML Collaborative Editing with Undo. In On the Move to Meaningful Internet Systems (OTM 2010). Springer. https://doi.org/10.1007/978--3--642--16934--2_37

[34]

Brice Nédelec, Pascal Molli, Achour Mostefaoui, and Emmanuel Desmontils. 2013. LSEQ: an Adaptive Structure for Sequences in Distributed Collaborative Editing. In 13th ACM Symposium on Document Engineering (DocEng). 37--46. https://doi.org/10.1145/2494266.2494278

Digital Library

[35]

David A Nichols, Pavel Curtis, Michael Dixon, and John Lamping. 1995. High-latency, low-bandwidth windowing in the Jupiter collaboration system. In 8th Annual ACM Symposium on User Interface and Software Technology (UIST 1995). ACM, 111--120. https://doi.org/10.1145/215585.215706

Digital Library

[36]

Petru Nicolaescu, Kevin Jahns, Michael Derntl, and Ralf Klamma. 2016. Near Real-Time Peer-to-Peer Shared Editing on Extensible Data Types. In 19th International Conference on Supporting Group Work (GROUP 2016). ACM, 39--49. https://doi.org/10.1145/2957276.2957310

Digital Library

[37]

Gérald Oster. 2016. wiki-transformation.md. https://gist.github.com/oster/04ca4fc1aaea7de58700

[38]

Gérald Oster, Pascal Molli, Pascal Urso, and Abdessamad Imine. 2006. Tombstone Transformation Functions for Ensuring Consistency in Collaborative Editing Systems. In 9th IEEE International Conference on Collaborative Computing (CollaborateCom 2006). IEEE. https://doi.org/10.1109/colcom.2006.361867

[39]

Gérald Oster, Pascal Urso, Pascal Molli, and Abdessamad Imine. 2006. Data Consistency for P2P Collaborative Editing. In ACM Conference on Computer Supported Cooperative Work (CSCW). https://doi.org/10.1145/1180875.1180916

Digital Library

[40]

François Pacull, Alain Sandoz, and André Schiper. 1994. Duplex: A Distributed Collaborative Editing Environment in Large Scale. In ACM Conference on Computer Supported Cooperative Work (CSCW 1994). ACM, 165--173. https://doi.org/10.1145/192844.192900

Digital Library

[41]

Nuno Preguiça. 2018. Conflict-free Replicated Data Types: An Overview. arXiv:1806.10254 https://arxiv.org/abs/1806.10254

[42]

Nuno Preguiça, Joan Manuel Marquès, Marc Shapiro, and Mihai Letia. 2009. A commutative replicated data type for cooperative editing. In 29th IEEE International Conference on Distributed Computing Systems (ICDCS). https://doi.org/10.1109/ICDCS.2009.20

Digital Library

[43]

Hyun-Gul Roh, Myeongjae Jeon, Jin-Soo Kim, and Joonwon Lee. 2011. Replicated abstract data types: Building blocks for collaborative applications. J. Parallel and Distrib. Comput. 71, 3 (March 2011), 354--368. https://doi.org/10.1016/j. jpdc.2010.12.006

[44]

Marc Shapiro, Nuno Preguiça, Carlos Baquero, and Marek Zawirski. 2011. Conflict-Free Replicated Data Types. In 13th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2011). ACM, 386--400. https://doi.org/10.1007/978--3--642--24550--3_29

[45]

Chengzheng Sun, Xiaohua Jia, Yanchun Zhang, Yun Yang, and David Chen. 1998. Achieving convergence, causality preservation, and intention preservation in real-time cooperative editing systems. ACM Transactions on Computer-Human Interaction 5, 1 (March 1998), 63--108. https://doi.org/10.1145/274444.274447

Digital Library

[46]

Chengzheng Sun, Steven Xia, David Sun, David Chen, Haifeng Shen, and Wentong Cai. 2006. Transparent Adaptation of Single-User Applications for Multi-User Real-Time Collaboration. ACM Transactions on Computer-Human Interaction 13, 4 (Dec. 2006), 531--582. https://doi.org/10.1145/1188816.1188821

Digital Library

[47]

Chengzheng Sun, Yi Xu, and Agustina Ng. 2017. Exhaustive Search and Resolution of Puzzles in OT Systems Supporting String-Wise Operations. In ACM Conference on Computer Supported Cooperative Work and Social Computing (CSCW 2017). ACM, 2504--2517. https://doi.org/10.1145/2998181.2998252

Digital Library

[48]

David Sun, Steven Xia, Chengzheng Sun, and David Chen. 2004. Operational Transformation for Collaborative Word Processing. In ACM Conference on Computer Supported Cooperative Work (CSCW 2004). ACM, 437--446. https://doi.org/10.1145/1031607.1031681

Digital Library

[49]

Robert H Thomas. 1979. A majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems 4, 2 (June 1979), 180--209. https://doi.org/10.1145/320071.320076

Digital Library

[50]

Stéphane Weiss, Pascal Urso, and Pascal Molli. 2009. Logoot: A Scalable Optimistic Replication Algorithm for Collaborative Editing on P2P Networks. In 29th IEEE International Conference on Distributed Computing Systems (ICDCS). 404--412. https://doi.org/10.1109/ICDCS.2009.75

Digital Library

[51]

Steven Xia, David Sun, Chengzheng Sun, David Chen, and Haifeng Shen. 2004. Leveraging Single-User Applications for Multi-User Collaboration: The CoWord Approach. In ACM Conference on Computer Supported Cooperative Work (CSCW 2004). ACM, 162--171. https://doi.org/10.1145/1031607.1031635

Digital Library

Cited By

Rabeshko YTurbal Y(2024)Performance optimisation techniques for Conflict-free Replicated Data Types (CRDT)Вісник Черкаського державного технологічного університету10.62660/bcstu/1.2024.2329:1(10-23)Online publication date: 18-Mar-2024
https://doi.org/10.62660/bcstu/1.2024.23
Ge SPark TZhu JHuang J(2023)Expressive Text-to-Image Generation with Rich Text2023 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV51070.2023.00694(7511-7522)Online publication date: 1-Oct-2023
https://doi.org/10.1109/ICCV51070.2023.00694

Index Terms

Peritext: A CRDT for Collaborative Rich Text Editing
1. Human-centered computing
  1. Collaborative and social computing
    1. Collaborative and social computing systems and tools
      1. Asynchronous editors
2. Information systems
  1. Information storage systems
    1. Storage management
      1. Version management

Recommendations

Undoing any operation in collaborative graphics editing systems
GROUP '01: Proceedings of the 2001 ACM International Conference on Supporting Group Work

Undo is a useful and widely supported feature which can be used to recover from erroneous operations, learn new system features, and explore alternative solutions. The ability to undo any operation at any time is especially important for collaborative ...
Read More
Scalable XML collaborative editing with undo
OTM'10: Proceedings of the 2010 international conference on On the move to meaningful internet systems - Volume Part I

Commutative Replicated Data-Type (CRDT) is a new class of algorithms that ensures scalable consistency of replicated data. It has been successfully applied to collaborative editing of texts without complex concurrency control.

In this paper, we present ...
Read More
Third annual collaborative editing workshop
GROUP '01: Proceedings of the 2001 ACM International Conference on Supporting Group Work

Collaborative editing systems support groups of people editing a document together over the computer network. People may work simultaneously on the same document, simultaneously on different copies of the document, or at different times on the original ...
Read More

Comments

Information & Contributors

Information

Published In

cover image Proceedings of the ACM on Human-Computer Interaction

Proceedings of the ACM on Human-Computer Interaction Volume 6, Issue CSCW2

CSCW

November 2022

8205 pages

EISSN:2573-0142

DOI:10.1145/3571154

Editor:
Jeff Nichols
Google

Issue’s Table of Contents

Copyright © 2022 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 11 November 2022

Published in PACMHCI Volume 6, Issue CSCW2

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
661
Total Downloads

Downloads (Last 12 months)532
Downloads (Last 6 weeks)70

Other Metrics

View Author Metrics

Citations

Cited By

Rabeshko YTurbal Y(2024)Performance optimisation techniques for Conflict-free Replicated Data Types (CRDT)Вісник Черкаського державного технологічного університету10.62660/bcstu/1.2024.2329:1(10-23)Online publication date: 18-Mar-2024
https://doi.org/10.62660/bcstu/1.2024.23
Ge SPark TZhu JHuang J(2023)Expressive Text-to-Image Generation with Rich Text2023 IEEE/CVF International Conference on Computer Vision (ICCV)10.1109/ICCV51070.2023.00694(7511-7522)Online publication date: 1-Oct-2023
https://doi.org/10.1109/ICCV51070.2023.00694

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

Media

Figures

Other

Tables

View Issue’s Table of Contents