Algorithms

We can class the RTC Algorithms into 3 main categories:

1. CRDT category doesn’t need a central server and is used by Riak, TomTom GPS, Teletype for Atom…

2. OT category needs a central server and is used by Google Docs, Office365…

3. Diffs category used by Cocalc…

Some implementations have a Mixed approach combining techniques of the above categories.

We also have an Others section for algorithm that don’t fit into those categories.

The following brings more perspective on how those categories compare.

• To OT or CRDT, that is the question and its references

• Collaborative Editing in CoCalc: OT, CRDT, or something else?

• Towards a unified theory of Operational Transformation and CRDT

• Differences between OT and CRDT

• I was wrong. CRDTs are the future (Hacker News discussion)

• Operational Transformation library?

• Real Differences Between OT and CRDT for Co-Editors

• Fluid framework, for building distributed, real-time collaborative web apps - You can read there: Adding more context: Fluid uses a mix of CRDT + OT to maintain state across multiple clients. I wrote a quick high level explanation of how Fluid uses eventual consistency and why it matters for real time collaboration (more details)

• Conclave - A private and secure real-time collaborative text editor

CRDT

About CRDT

CRTD is an ancronym for Conflict-free Replicated Data Type. CRDT doesn’t need a central server and is used by Riak, TomTom GPS, Teletype for Atom. CRDT is about Shared Data Structures.

• CRDT on Wikipedia

• Y.js README

• CRDT.tech

• Creating a Collaborative Editor

• A simple approach to building a realtime collaborative text editor

The following videos are useful to discover CRTD in relationship with OT.

• Conflict Resolution for Eventual Consistency

• CRDTs and the Quest for Distributed Consistency

• CRDTs for Non Academics

CRDT is strongly eventual consistent:

• https://medium.com/@amberovsky/crdt-conflict-free-replicated-data-types-b4bfc8459d26

• https://medium.com/@naveennegi/rendezvous-with-riak-crdts-part-1-e94cfc8fe091

• https://medium.com/@dmitrymartyanov/crdt-for-data-consistency-in-distributed-environment-ddb8dfdbc396

CRDT can use Version Vectors to assign versions that indicate how many changes have been made by a user.

You can also jump into the following links to get more details.

• https://www.youtube.com/watch?v=jIR0Ngov7vo

• https://arxiv.org/abs/1608.03960

• https://dl.acm.org/doi/10.1145/3359141

• https://github.com/yjs/yjs#Yjs-CRDT-Algorithm

• https://www.researchgate.net/publication/310212186_Near_Real-Time_Peer-to-Peer_Shared_Editing_on_Extensible_Data_Types

• https://www.serverless.com/blog/crdt-explained-supercharge-serverless-at-edge

• https://www.infoq.com/presentations/crdt-production

• https://www.infoworld.com/article/3305321/when-to-use-a-crdt-based-database.html

• https://www.figma.com/blog/how-figmas-multiplayer-technology-works

• https://github.com/alangibson/awesome-crdt

CRDT has some edge cases: The Hard Parts and its references (slides - 1h10m video - hacker news discussion).

RGA Split is a High Responsiveness for Group Editing CRDTs.

Some post-mortem stories can be instructive: xi-editor link 1 and xi-editor link 2.

Other information:

• CRDT is used in Apache Cassandra.

• Are CRDTs suitable for shared editing? (Hacker News Discussion).

CRDT Libraries

JupyterLab RTC integration is relying on the CRDT Implementation provided by Lumino Datastore. The Lumino Datastore library is also used in e.g. the interactive dashboard editor for JupyterLab.

Y.js is a CRDT implementation. Checkout out How Yjs works from the inside out video and the online demos:

• https://yjs.dev

• https://demos.yjs.dev

• https://github.com/yjs/yjs-demos

Read more on the Y.js discussion site and the Y.js blog (backed by tag1consulting) and lib0 encoding (lib0 repo).

Automerge is a JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.

• Performance Preview: Automerge binary data format.

• Collaborative editing to CodeMirror by linking it to an Automerge.Text object.

• Automerge-rs is a Rust implementation.

• Persistence with mpl or hypermerge.

Applications examples using Automerge are available: pushpin (live), pixel pusher ([DEPRECATED] trelli).

Teletype CRDT is string-wise sequence CRDT powering peer-to-peer collaborative editing in Teletype for Atom.

Local First (by jaredforsyth) is nested object CRDT, a hybrid logical clock with a rich-text CRDT.

CRDT-sequence (by @phedkvist), with a server.

Logux has features inspired by CRDT to resolve edit conflicts between users. Real-time updates to prevent conflicts. Time travel to keep actions order the same on every client. A distributed timer to detect the latest changes. It provides a Server and a client.

Rust CRDT is a family of CRDT’s supporting both State and Op based replication..

OT

About OT

OT is an acronym for Operational Transformation. OT needs a central server and is used by Google Docs, Office365..

• Operational Transformation on Wikipedia

• Building a real-time collaborative editor using Operational Transformation

• Operational Transformation, the real time collaborative editing algorithm

Transformation Property TP2 Case.

• http://www.thinkbottomup.com.au/site/blog/Google_Wave_Intention_Preservation_Branching_Merging_and_TP2

• http://www.thinkbottomup.com.au/site/blog/Google_Wave_Operational_Transform_and_Server_Acknowledgments

• https://blog.cocalc.com/2018/10/11/collaborative-editing.html

Read more on CKEditor lessons learned and other Libraries for OT.

OT Libraries

ShareDB is a realtime database backend based on Operational Transformation (OT) of JSON documents. It is the realtime backend for the DerbyJS web application framework.

• https://github.com/startupjs/startupjs

• https://github.com/startupjs/startupjs/tree/master/packages/react-sharedb

• [DEPRECATED] https://github.com/dmapper/react-sharedb

• [DEPRECATED] https://github.com/josephg/ShareJS

• [DEPRECATED] https://sharejs.org

OT.js is not maintained anymore.

Diffs

About Diffs

Diffs is more a family of protocols that rely on exchange and merge of diffs. It is used by e.g. Cocalc. Read more on this in the following.

• Differential Synchronization (research paper).

• Diffs and Merge.

Diffs Libraries

Google Diff-Match-Patch offers robust algorithms to perform the operations required for synchronizing plain text. See also JackuB Diff-Match-Patch.

Diff-Sync library. See the diffsync-todos example deployed on heroku.

Mixed

Microsoft Fluid

Microsoft Fluid has been announced in May 2020 (see also this doc). It is now released.

The offered functionalities and how it can be used outside of Microsoft Office 365 are investigated in jupyterlab/rtc#80.

From the Fluid FAQ:

• Does Fluid use operational transforms? Fluid does not use Operational Transforms (OT), but we learned a tremendous amount from the literature on OT. While OT uses operations that can be applied out of order by transforming operations to account for recent changes, Fluid relies on a Total Order Broadcast to guarantee that all operations are applied in a specific order.

• Does Fluid use CRDT? Fluid does not use Conflict-Free Replicated Data Types (CRDTs), but our model is more similar to CRDT than OT. The Fluid Framework relies on update-based operations that are ordered using our Total Order Broadcast to prevent conflicts. This allows us to have non-commutative operations because there is an explicit ordering.

On Twitter.

• https://twitter.com/TSteveLuc/status/1304127430743924736

• https://twitter.com/mattetti/status/1304233818576969729

• https://twitter.com/martinkl/status/1304166170812190720

Other information.

• Introducing distributed data structures.

• How a Fluid Framework service works.

• Deploy and run your own Fluid Framework service.

• Fluid framework, for building distributed, real-time collaborative web apps (quote: “Adding more context: Fluid uses a mix of CRDT + OT to maintain state across multiple clients. I wrote a quick high level explanation of how Fluid uses eventual consistency and why it matters for real time collaboration”).

• Solving Real Time Collaboration Using Eventual Consistency.

Others

We review here other algorithms and techniques in the broader Distributed Computing domain that could be useful for RTC.

Paxos

• https://en.wikipedia.org/wiki/Paxos_(computer_science)

• https://en.wikipedia.org/wiki/Gossip_protocol

Vector Clocks

• https://en.wikipedia.org/wiki/Vector_clock

• https://www.datastax.com/blog/2013/09/why-cassandra-doesnt-need-vector-clocks