Differential Synchronization

Channel:Google TechTalks · Length:54:43 · Published:2009-01-10 · Views:52090

Watch on YouTube

Summary

Neil Fraser of Google presents Differential Synchronization, the algorithm behind MobWrite, for keeping multiple copies of a document in sync in real time. The talk argues the approach is robust, convergent and efficient.

Why HN recommends it

HN points to it as a simple diff-and-patch alternative to operational transforms and CRDTs for collaborative editing.

The really nice bits, though, are that it is a simple algorithm — HN, 2014

Distributed systems · Algorithms & data structures

Subtitles (excerpt)

thanks for coming uh this talk is going to be mostly on the Whiteboard so forgive me if my back has turned um interrupt me for questions at any time please the more the merrier um the question means you don't understand something but it also means that you still care so that's good and uh this talk is going out on YouTube so uh hold the confidential questions until the end um okay differential synchronization the purpose of it is if we have multiple users all looking and all editing the same document let's say uh document says cat and we've got three users one two and three if we have real time synchronization then if user one adds an S to cats user two changes this to my cats then the S gets pushed across to here the my goes back and is merged and the S goes over here and the my comes down and so everybody is always looking at close to the same text now there's always going to be some latency so no so two people may have different things on screen and any given time um I mean the speed of light is going to dictate that there's at the very minimum going to be some difference um but the idea is that it should very quickly resolve itself now this diagram clearly screams out peer-to-peer um unfortunately per perod doesn't

On Hacker News

I'm working on a project with some offline data synchronization needs, but haven't started implementation yet. I've been following CRDTs with interest. I also saw many of the same downsides mentioned in the OP, e.g. bloat (which apparently are being addressed remarkably well). Beyond OT, another approach I've run across that looks very promising is Differential Synchronization[1] by Neil Fraser. … — mhale, 2020-09
I've not tried it, but you might also be interested in an approach called differential synchronization[1]. Basically, it's just a specific way of passing diffs around to guarantee convergence, though (as far as I can tell) it doesn't guarantee much else (as in do you lose data if a patch can't be applied?). The really nice bits, though, are that it is a simple algorithm and that it can be applied… — dahjelle, 2014-06
One real-world use case is differential synchronization. Here's a Google Tech Talk on the subject: [VIDEO] This is for real-time collaborative editing or replication of structured data (unlike Operational Transformation, which is optimized for text). Sending patches back and forth is at the core of the protocol. — raganwald, 2012-09
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: [VIDEO] . The trick is sync after someone changes the document while including a short debounce s… — pg_bot, 2018-07

Related videos