Heather McLean

I’ll admit this is a little bit of geek porn today, different from my usual fare. Google has released a new algorithm for sending software updates dubbed Courgette. In particular, I found the section on “guessing” intriguing:

We can think of a differential update as a prediction followed by a correction, a kind of guessing game.  In its simplest form (just bsdiff / bspatch), the client has only a dumb guess, ‘original’, so the server sends a binary diff to correct ‘original’ to the desired answer, ‘update’.  Now what if the server could pass a hint that could be used to generate a better guess, but we are not sure the guess will be useful?  We could insure against losing information by using the original and the guess together as the basis for the diff…

This system has some interesting properties.  If the guess is the empty string, then we have the same diff as with plain bsdiff.  If the guess is perfect, the diff will be tiny, simply a directive to copy the guess.

A predictive software update engine has some interesting potential. I would love to see with what kind of accuracy their algorithm can actually “guess” the correct patch.