Bartosz Sypytkowski

Author here. Its because I've been focussing on collaborative text editing first, and a fair few of the articles which pop up on HN were written by me.

There's more great CRDT writing which deserves some attention. For example, this series by Bartosz Sypytkowski is long but excellent:

https://bartoszsypytkowski.com/the-state-of-a-state-based-crdts/

He talks about CRDTs from the ground up, from much more of a mathematical / FP point of view. I learned a lot reading this series!

Why have I been focussing on collaborative text editing? Because I think performance has been the #1 blocker stopping us from using CRDTs in most software. And text CRDTs are a canary in the coal mine for performance. Uh, thats a tortured metaphor. I mean, If we can make text CRDTs fast, we can make everything fast.

And JSON editing (what everyone actually wants) needs to embed text editing anyway. So we've sort of gotta do that first anyway.

Smart people have also been working on the JSON editing problem. I'm a big fan of Greg Little's Shelf algorithm[1] for last-writer-wins JSON editing (which is what people usually want). Shelf is simple enough you can implement it in less than 100 lines of code. But shelf doesn't support collaborative list or text editing (text is a list of characters). We need all of these pieces, then we need to mush them all together in a sensible way. And thats something Yjs and automerge both already do, and do quite well.

Ah, I'll put it in as a note in the beginning. You can see a more basic introduction in a previous post I wrote:

https://interjectedfuture.com/trade-offs-between-different-crdts/

https://news.ycombinator.com/item?id=38916647

Here's some introductory material I found helpful:

- [An interactive intro to CRDTs](https://jakelazaroff.com/words/an-interactive-intro-to-crdts/)

- [An introduction to state-based CRDTs](https://www.bartoszsypytkowski.com/the-state-of-a-state-based-crdts/)

- [CRDTs for non-academics](https://www.youtube.com/watch?v=vBU70EjwGfw)

- [CRDT: The Hard Parts](https://www.youtube.com/watch?v=x7drE24geUw)

- [Readings in CRDTs](https://christophermeiklejohn.com/crdt/2014/07/22/readings-in-crdts.html)

- [crdt.tech](https://crdt.tech)

I think you could encode a “shelf” last-write-wins CRDT into your HTML using data attributes without exploding your file size. You would need to add a data-version attribute, and if you want to support hand-editing or editing by programs that don’t understand the CRDT, a CRC32 or other parity as data-parity so your loader can tell when a user might have edited a row without updating data-version.

Shelf is really simple - the JS implementation is tiny (https://github.com/dglittle/shelf) and a walkthrough of the algorithm here is a quick read: https://bartoszsypytkowski.com/shelf-crdt/amp/

It wouldn’t handle character level sync - but would let you merge documents at a rows/items/blocks level.

I have implemented a JSON-like CRDT using this nice tutorial [1], which is a tree, but never an append-only DAG.

I'm curious how two edges meeting the same vertex will make it difficult to resolve the conflict automatically? Is it that two users will create the same vertex (concurrently) with slightly different attributes, and attribute-merging requires human-in-the-loop?

Of course if the DAG is not append-only, but supports, say, "moving" of edges/branches, it is a totally different problem. Martin has something to say about this [2].

[1] https://www.bartoszsypytkowski.com/operation-based-crdts-json-document/
[2] https://martin.kleppmann.com/papers/move-op.pdf

I have many recommendations of different kinds:

## Blogs:

- http://muratbuffalo.blogspot.com/

- https://bartoszsypytkowski.com/

- https://decentralizedthoughts.github.io/

- https://www.the-paper-trail.org/

- https://blog.acolyer.org/

- https://pathelland.substack.com/

## Other web resources

- https://aws.amazon.com/builders-library/ - set of resources from Amazon about building distributed systems

- https://www.youtube.com/playlist?list=PLeKd45zvjcDFUEv_ohr_HdUFe97RItdiB - lecture series from Cambridge

## Books

- https://www.cl.cam.ac.uk/teaching/1213/PrincComm/mfcn.pdf - A great book on the maths of networking (probability, queuing theory etc...)