Differential Synchronization (2009) | Hacker News Reader

Differential Synchronization (2009)

neil.fraser.name

56 pointsdhotson10 comments

Some related work includes operational transformation (https://en.wikipedia.org/wiki/Operational_transformation), and Darcs' patch theory (https://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theo...).

We’re looking seriously at using this at work. Is anyone aware of any OSS implementations?

The reference implementation is MobWrite: https://code.google.com/archive/p/google-mobwrite/

The project got put to one side when Google Code shut down, but I dusted it off last month and everything still works.

It seems equivalent without loss of valuable properties to the conflict/rebase approach described here[0], and while it probably could be adapted to a p2p setting, the space requirements seem like they would not scale as well as the CRDT-based approaches like RGASplit[1].

What are your thoughts on competing algorithms?

[0]: http://marijnhaverbeke.nl/blog/collaborative-editing.html

[1]: https://github.com/atom/teletype-crdt

Wanting to know this too!

Thanks for the reply, and the code!

Morgan Dixon implemented with me once. Be aware that as define, it is limited to updating at a fixed polling interval. So you don't get updates as each party types; you have to wait for the round-trip sync update every 100ms (or whatever you configure it to).

Differential synchronization does not require a fixed polling interval. You can have real time updates as each party types, in fact the algorithm prefers this setup as it is easier to process a lot of small changes rapidly. Neil goes into further detail in this google talk about why this is the case: https://youtu.be/S2Hp_1jqpY8?t=2815. The trick is sync after someone changes the document while including a short debounce so that you aren't overloading the system with superfluous edits.

Thanks! Good point!

Neil Fraser went on to apply this work at Google with Google Docs (Operational Transformation, see other comment here).

He was also one of my heroes that inspired my work to build a decentralized (and offline-first) version, that I later applied to graphs with https://github.com/amark/gun .

Some good follow ups are:

- Martin Kleppmann's https://youtu.be/yCcWpzY8dIA?t=29m36s

- Cartoon explainer http://gun.js.org/explainers/school/class.html

Reply on news.ycombinator.com