Improved Single-Round Protocols for Remote File Synchronization

Abstract—Given two versions of a file, a current version located on one machine and an outdated version known only to another machine, the remote file synchronization prob-lem is how to update the outdated version over a network with a minimal amount of communication. In particular, when the versions are very similar, the total data transmit-ted should be significantly smaller than the file size. File synchronization problems arise in many application scenar-ios such as web site mirroring, file system backup and repli-cation, and web access over slow links. An open source tool for this problem, called rsync and included in many Linux distributions, is widely used in such scenarios. rsync uses a single round of messages between the two machines. While recent research has shown that significant additional sav-ings in bandwidth consumption are possible through the use of optimized multi-round protocols, there are many scenar-ios where multiple rounds are undesirable. In this paper, we study single-round protocols for file synchronization that offer significant improvements over rsync. Our main contribution is a new approach to file syn-chronization based on the use of erasure codes. Using this approach, we design a single-round protocol that is prov-ably efficient with respect to common measures of file dis-tance, and another optimized practical protocol that shows promising improvements over rsync on our data sets. In addition, we show how to obtain some improvements by en-gineering the rsync approach, and study the use of recent set reconciliation techniques in file synchronization protocols. I