4 ms·

Differential Synchronization (2009)

56 points by dhotson 8y ago

sctb 8y ago
Some related work includes operational transformation (https://en.wikipedia.org/wiki/Operational_transformation https://en.wikipedia.org/wiki/Operational_transformation), and Darcs' patch theory (https://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory https://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theo...).
marknadal 8y ago
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 https://github.com/amark/gun . Some good follow ups are: - Martin Kleppmann's https://youtu.be/yCcWpzY8dIA?t=29m36s https://youtu.be/yCcWpzY8dIA?t=29m36s - Cartoon explainer http://gun.js.org/explainers/school/class.html http://gun.js.org/explainers/school/class.html
delinka 8y ago
We’re looking seriously at using this at work. Is anyone aware of any OSS implementations?
- NeilFraser 8y ago
  The reference implementation is MobWrite: https://code.google.com/archive/p/google-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.
  - espadrine 8y ago
    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 http://marijnhaverbeke.nl/blog/collaborative-editing.html [1]: https://github.com/atom/teletype-crdt https://github.com/atom/teletype-crdt
    - jlu 8y ago
      Wanting to know this too!
  - deleted 8y ago
    [deleted]
  - delinka 8y ago
    Thanks for the reply, and the code!
- toomim 8y ago
  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).
  - pg_bot 8y ago
    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 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.
    - toomim 8y ago
      Thanks! Good point!

56 points by dhotson 8y ago

sctb 8y ago

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

marknadal 8y ago

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 https://github.com/amark/gun . Some good follow ups are: - Martin Kleppmann's https://youtu.be/yCcWpzY8dIA?t=29m36s https://youtu.be/yCcWpzY8dIA?t=29m36s - Cartoon explainer http://gun.js.org/explainers/school/class.html http://gun.js.org/explainers/school/class.html

delinka 8y ago

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

NeilFraser 8y ago
The reference implementation is MobWrite: https://code.google.com/archive/p/google-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.
- espadrine 8y ago
  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 http://marijnhaverbeke.nl/blog/collaborative-editing.html [1]: https://github.com/atom/teletype-crdt https://github.com/atom/teletype-crdt
  - jlu 8y ago
    Wanting to know this too!
- deleted 8y ago
  [deleted]
- delinka 8y ago
  Thanks for the reply, and the code!
toomim 8y ago
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).
- pg_bot 8y ago
  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 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.
  - toomim 8y ago
    Thanks! Good point!