4 ms·

For context, one of the main motivations for CRDT was multiple users simultaneously editing some document. E.G. Google Docs. I was researching these approaches

For context, one of the main motivations for CRDT was multiple users simultaneously editing some document. E.G. Google Docs. I was researching these approaches when I was implementing my own collaborative text editor. CRDT was too mathematically steep for me. Another approach is differential syncing. I think Google Docs was originally implemented with differential syncing and then switched to CRDT. https://static.googleusercontent.com/media/research.google.com/en//pubs/archive/35605.pdf https://static.googleusercontent.com/media/research.google.c... I think the tradeoff and why I leaned towards differential syncing was that the implementation was easier. There are some gaps / unclear implementation details in this white paper's algorithm that you kind of have to rediscover yourself, because if you followed the algorithm listed here it will not work. I forgot the details. I'm still not sure if that was intentional. I hope now the literature on CRDT has gotten more mainstream and digestible for non-mathematicians because that seems like the future.

thesz 5y ago
From what I know, Google Docs never used CRDT. They adopted Google Wave's algorithm which was taken from Jupiter UI system [1]: operational transformations [2] with conflict resolution on the server side. [1] https://svn.apache.org/repos/asf/incubator/wave/whitepapers/operational-transform/operational-transform.html https://svn.apache.org/repos/asf/incubator/wave/whitepapers/... [2] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation When the server does ordering operation, operational transformations became a piece of cake to implement and reason about. If you add hierarchical addressing like "book/chapter/section/subsection/paragraph/char", they are also quite conflict free. But you need a central authority. In case of Google, it is easy and fits the profit model. Bonus: https://code.google.com/archive/p/google-mobwrite/ https://code.google.com/archive/p/google-mobwrite/ A library to collaboratively edit HTML forms.

thesz 5y ago

From what I know, Google Docs never used CRDT. They adopted Google Wave's algorithm which was taken from Jupiter UI system [1]: operational transformations [2] with conflict resolution on the server side. [1] https://svn.apache.org/repos/asf/incubator/wave/whitepapers/operational-transform/operational-transform.html https://svn.apache.org/repos/asf/incubator/wave/whitepapers/... [2] https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation When the server does ordering operation, operational transformations became a piece of cake to implement and reason about. If you add hierarchical addressing like "book/chapter/section/subsection/paragraph/char", they are also quite conflict free. But you need a central authority. In case of Google, it is easy and fits the profit model. Bonus: https://code.google.com/archive/p/google-mobwrite/ https://code.google.com/archive/p/google-mobwrite/ A library to collaboratively edit HTML forms.