The rsync algorithm
Australian National University
Canberra, ACT 0200,
This report presents an algorithm for updating a file on one machine to be
identical to a file on another machine. We assume that the two machines are
connected by a low-bandwidth high-latency bi-directional communications link.
The algorithm identifies parts of the source file which are identical to some
part of the destination file, and only sends those parts which cannot be matched
in this way. Effectively, the algorithm computes a set of differences without
having both files on the same machine. The algorithm works best when the files
are similar, but will also function correctly and reasonably efficiently when
the files are quite different.