1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2 Final//EN">
2 <!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)
3 originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds
4 * revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan
5 * with significant contributions from:
6 Jens Lippmann, Marek Rouchal, Martin Wilck and others -->
9 <TITLE>The rsync algorithm</TITLE>
10 <META NAME="description" CONTENT="The rsync algorithm">
11 <META NAME="keywords" CONTENT="tech_report">
12 <META NAME="resource-type" CONTENT="document">
13 <META NAME="distribution" CONTENT="global">
14 <META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=iso-8859-1">
15 <LINK REL="STYLESHEET" HREF="tech_report.css">
16 <LINK REL="next" HREF="node1.html">
19 <!--Navigation Panel-->
22 <IMG WIDTH="37" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="next"
23 SRC="/usr/local/src/latex2html/icons.gif/next_motif.gif"></A>
24 <IMG WIDTH="26" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="up"
25 SRC="/usr/local/src/latex2html/icons.gif/up_motif_gr.gif">
26 <IMG WIDTH="63" HEIGHT="24" ALIGN="BOTTOM" BORDER="0" ALT="previous"
27 SRC="/usr/local/src/latex2html/icons.gif/previous_motif_gr.gif">
29 <B> Next:</B> <A NAME="tex2html5"
30 HREF="node1.html">The problem</A>
33 <!--End of Navigation Panel-->
40 <H1 ALIGN="CENTER">The rsync algorithm</H1>
41 <P ALIGN="CENTER"><STRONG>Andrew Tridgell Paul Mackerras
43 Department of Computer Science <BR>
44 Australian National University <BR>
45 Canberra, ACT 0200, Australia</STRONG></P>
52 This report presents an algorithm for updating a file on one machine
53 to be identical to a file on another machine. We assume that the
54 two machines are connected by a low-bandwidth high-latency
55 bi-directional communications link. The algorithm identifies parts
56 of the source file which are identical to some part of the
57 destination file, and only sends those parts which cannot be matched
58 in this way. Effectively, the algorithm computes a set of
59 differences without having both files on the same machine. The
60 algorithm works best when the files are similar, but will also
61 function correctly and reasonably efficiently when the files are
67 <!--Table of Child-Links-->
68 <A NAME="CHILD_LINKS"> </A>
70 <LI><A NAME="tex2html6"
71 HREF="node1.html">The problem</A>
72 <LI><A NAME="tex2html7"
73 HREF="node2.html">The rsync algorithm</A>
74 <LI><A NAME="tex2html8"
75 HREF="node3.html">Rolling checksum</A>
76 <LI><A NAME="tex2html9"
77 HREF="node4.html">Checksum searching</A>
78 <LI><A NAME="tex2html10"
79 HREF="node5.html">Pipelining</A>
80 <LI><A NAME="tex2html11"
81 HREF="node6.html">Results</A>
82 <LI><A NAME="tex2html12"
83 HREF="node7.html">Availability</A>
84 <LI><A NAME="tex2html13"
85 HREF="node8.html">About this document ... </A>
87 <!--End of Table of Child-Links-->
90 <I>Andrew Tridgell</I>