Abstract:

Imagine that you have a file F and your friend elsewhere has a
possibly outdated version F' of the file.  You want to update
F', but the network has a limited bandwidth, and F is too big to
be sent over as is.  It would be desirable to send him only the
new parts.  But you don't know his version.  What can you do?
This is just an instance of an important file synchronization
problem.  In general you may need to update numerous locations
and you may need the work to be done automatically.  The problem
is complex and has many facets.  The speaker was a part of a
Microsoft team that came up with a novel and efficient solution
of the synchronization problem which is a part of the
Distributed File System Replication in Windows Server 2003 R2,
and which is used in the Sharing Folders feature of MSN Instant
Messenger 8, currently in a world-wide beta test.

But let's return to the first scenario above.  You can do the
following. Chop F into chunks and send to your friend hashes of
the chunks.  Your friend chops F', decides which of your chunks
he needs and asks for them. You send him the required chunks.
This idea is not new.  We describe the prior art and our
improvements, in particular a novel way to chop files. We
analyze the problem and discuss its complexity from various
angles. This part of the synchronization project is joint work
with Nikolaj Bjorner and Andreas Blass.