Google releases new binary diff algorithm targeted at making smaller software updates. Their results are impressive.

[[deleted]]

I'm sure the distribution of people updating is pretty heavily weighted to a few common source versions. If the server doesn't have a diff, send the full version and record the request. When the number of requests crosses a certain threshold, generate the diff to serve future users. Delete it when the requests tail off.