Google Wave’s algorithm is now used by Google Docs, it’s Operational Transformation (OT) [1]. You can approximately view it as a special form of CRDT but the theory underpinning each have separate origins.
OT is efficient and fast at real-time editing with a central server, whereas CRDTs are more capable in distributed/p2p scenarios but bring significant overhead as they store a lot of metadata.
My understanding is that most specifications for OT have obscure failure cases if a central server is not used. Some papers have fixed these issues to enable fully P2P OT, but IIRC the resulting ops require similar amounts of metadata per-change as sequence CRDTs.
Interesting. I thought that OT implementations require peers to have at least one authoritative view of the transformations somewhere, and then distribute different operation sequences (after transformed) to different node. That, in simplest way, would imply a central server (otherwise you will have an alternative method to communicate the authoritative view between peers, which sort of defeat the purpose).
Yes. There do exist peer-to-peer OT algorithms, however they have not become popular in any production websites.
The popular production systems (such as Google Wave and Docs) are based on the Jupiter style of operational transform, which features a single central server, with a single line of time. The clients try to send their edits to the server as the most-recent edit. If they fail, for instance because another client has made an edit, then they rebase their edit on the new most-recent version, and then try to submit it again.
Keep in mind that OT and CRDT aren't actually algorithms -- they are perspectives from which a programmer might try to think of an algorithm.
The Operational Transform perspective says "think about how you can transform your edits (aka operations) so that they work when applied in a different order, on a peer with a different history of time.
The CRDT perspective says "think about how you can formulate your data structures so that you can apply any edit in any order."
In practice, programmers who took OT perspective were able to create mostly-working systems pretty easily. But getting full consistency (aka correctness) was very difficult, because it was difficult to think of all the ways in which multiple operations could interleave and affect one another, especially without the constraint of a central. Thus, it took many, many academic papers before anyone succeeded in coming up with a fully P2P algorithm that resulted in consistent synchronization after arbitrary edits.
This frustrated many of the academics enough for them to change their perspective. The first step towards this was a system called WOOT, which stands for "With-Out Operational Transform", where the researchers explicitly gave up on their old perspective, and started thinking along the CRDT paradigm.
The CRDT paradigm made it easy to get fully-consistent peer-to-peer systems. However, it has remained elusive to make one that's performant enough to be used in practice. They tend to require holding onto the entire history of all operations that have ever occurred, and each operation itself tends to require 10x or 100x overhead. Thus, you can edit a small text document and quickly end up with megabytes of data for a small string of text.
But there's a third paradigm here that isn't discussed as much -- Version Control. Think about git. It provides a DAG of versions over time, that branch and fork, and a way to consistently merge any two versions. From this perspective, it turns out that OT is the discovery of the rebase operation, and CRDT is the discovery of multi-way merge in a DVCS. OT people have been trying to simplify complicated merges by doing clever rebasing. This is much easier with a central server, and it happens to allow you to clean up old history more easily, which saves a lot of memory, making it useful in production systems.
In practice, I think that these three perspectives are all going in the same direction. If you build an OT system, and then try to make it fully consistent and peer-to-peer, you end up with CRDT algorithms. If you build a CRDT, and want more flexibility in memory requirements, a great approach is to throw a server into the mix and rebase (aka transform some operations). And git already has "operational transform" and "CRDT" algorithms in it.
My personal interest is in unifying these algorithms in the https://braid.news project. We have a unified protocol that allows OT and CRDT systems to communicate with one another, and we've got some great new algorithms for pruning old history in a fully-p2p network that I expect to release this summer.
OT is efficient and fast at real-time editing with a central server, whereas CRDTs are more capable in distributed/p2p scenarios but bring significant overhead as they store a lot of metadata.
1) https://en.m.wikipedia.org/wiki/Operational_transformation