Differential Synchronization
Channel:Google TechTalks · Length:54:43 · Published:2009-01-10 · Views:52090
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
- The End of Suburbia - 52 minute documentary on peak oil · endofsuburbia · 51:44
- ReactiveConf 2017 - Tom Dale: Secrets of the Glimmer VM · ReactiveConf · 33:23
- The Soul of Erlang and Elixir • Sasa Juric • GOTO 2019 · GOTO Conferences · 42:02
- "Testing Distributed Systems w/ Deterministic Simulation" by Will Wilson · Strange Loop Conference · 40:20
- CppCon 2017: Matt Kulukundis “Designing a Fast, Efficient, Cache-friendly Hash Table, Step by Step” · CppCon · 59:33
- Erlang Factory 2014 - That's 'Billion' with a 'B': Scaling to the Next Level at WhatsApp · Erlang Solutions · 49:15
- "Turning the database inside out with Apache Samza" by Martin Kleppmann · Strange Loop Conference · 47:42
- The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever? · Reducible · 28:23
- Modern Dictionaries by Raymond Hettinger · SF Python · 1:07:41
- The Language of the System - Rich Hickey · ClojureTV · 1:02:49
- Google I/O 2012 - Go Concurrency Patterns · Google for Developers · 51:27
- Conflict Resolution for Eventual Consistency • Martin Kleppmann • GOTO 2016 · GOTO Conferences · 51:35
- "Unison: a new distributed programming language" by Paul Chiusano · Strange Loop Conference · 41:05
- CppCon 2014: Chandler Carruth "Efficiency with Algorithms, Performance with Data Structures" · CppCon · 1:13:41
- CppCon 2017: Juan Pedro Bolivar Puente “Postmodern immutable data structures” · CppCon · 1:05:59
- Sorting Algorithms: Speed Is Found In The Minds of People - Andrei Alexandrescu - CppCon 2019 · CppCon · 1:29:55