Hacker News new | past | comments | ask | show | jobs | submit login

> So is the gist of it that OT relies on central servers and they all use OT rather than CRDT?

You are right. I'd take shot at blowing out the why part. Practically, real-time collaboration apps can be categorized into two:

#1 The document editors, which stores information on the cloud. I'll refer these as document editors henceforth.

#2 The ones that doesn't need a thick server, except for broadcasting edits. Like plain text editors and code editors. I'll refer these as code editors for simplicity sake.

Both have a slightly different set of problems.

Document editors, usually have a slightly richer document representation schema (since most of them are rich text documents anyway). But they have the luxury of a central server. A central server means, now they have the power for good versioning, rollbacks to a consistent state, picking winners and ensuring ordering of edits when syncing large edits.

Code editors, although their doc representation is usually arrays of characters (it could be strings, ropes, or whatever but essentially just a set of characters), these don't have the luxury of a central server that could decide a winner when concurrent edits take place. This means the clients have to be very intelligent and converge to the same representation no matter how out-of-order the edits arrive.

Now coming back to the two algorithms camps - OT & CRDT:

The general outlook is that, OT - while being simple, they have this classic TP2 problem that would make it harder to arrive at a consistent state eventually - without a help from a central server. The alternative is to have a complicated system, almost as complicated as CRDTs. (More about this can be read through the Internet. If anybody's interested I'll post links to stuff I've read through)

CRDT - CRDT have (or maybe had?) a strong reputation of being efficient at arriving at a consistent state with out of order edits. They can do it, because basically no characters in a CRDT document is deleted anyway (they are just marked deleted and are termed tombstones). So no information loss, which means a clever algorithm can write a function to easily arrive at a consistent state at each site. This means, a central server is now only optional.

If I didn't lose you until now, you'd have intuitively guessed why document editors, tended to always pick OT and code editors prefer CRDT over OT.

This is complete oversimplifications and certainly there's a ton of things I left out for simplicity sake.

Source: I'm in the business of building a powerful Google Docs alternative, a word processor that runs on the browser: https://writer.zoho.com (Zoho Writer)




> The general outlook is that, OT - while being simple, they have this classic TP2 problem that would make it harder to arrive at a consistent state eventually - without a help from a central server. The alternative is to have a complicated system, almost as complicated as CRDTs.

Well this characterization isn't quite right. With regard to TP2, this is a solved problem, with or without using a server. Most of the conversations around TP2 seems to miss the crucial point that TP2 is not needed for convergence. CRDT academic literature has largely been responsible for propagating the notion that TP2 is a must for every OT system - without TP2, all is lost -- this is a myth. I wrote about it extensively here [1].

This article [2] gives an analysis of 7 coeditors based on OT, including the likes of Google Docs, showing that they avoid having to design transformation functions that require TP2. Some of the systems are fully de-centralized [3], others require a server.

It is also worth making a finer distinction between systems that do need a central server -- there are "transformation servers" and "messaging severs". Google Docs, for example, demands that its servers perform some portion of the transformation logic. Many other solutions rely on using the server only for message transmission/serialization, thus the server side logic is significantly simpler.

[1] https://arxiv.org/pdf/1905.01302.pdf

[2] Achieving convergence in operational transformation: conditions, mechanisms, and systems.ACM CSCW (2014)

[3] A generic operation transformation scheme for consistency maintenance in real-time cooperative editing systems ACM GROUP (1997)




Guidelines | FAQ | Support | API | Security | Lists | Bookmarklet | Legal | Apply to YC | Contact

Search: