CAREER: Practical Data Synchronization: Minimizing Communication

The problem of data synchronization is inherent to systems that require consistency among distributed information. In light ofthe vision of pervasive computing, in which any two mobile or fixed computing devices would be able tointeract, data synchronization is increasingly becoming an essential technology. To date, most research on data synchronization has focused on database issues related to conflict resolution. However, we feelthat current trends towards pervasive computing point to communication becoming the primary bottleneck for synchronization. For example, the Palm Pilot IIIxe, a popular and representative Personal Digital Assistant, can take even 20 minutes to synchronize with a desktop PC in certain practical scenarios. There are many other diverse examples of the need for communication-aware data synchronization, including synchronization of mobile data, resource discovery, and even reconciliation of nucleotide sequences in DNA.

We intend to investigate practical data synchronization techniques that minimize communication complexity, building upon a foundation of recent research connecting such techniques to graph coloring problems and the design of error-control codes. These connections allow for application of the latest results in these fields, such as the capacity-approaching Low Density Parity-Check codes, to important synchronization issues. The synchronized schemes we propose to research promise to be much faster and more general than those currently in use, offering applications to fault-tolerance, file synchronization, and image comparison. At the same time, we outline an ambitious, but attainable, educational plan based on years of experience with a diverse body of students. Our goals include: 1) strengthening ties with high schools through mentoring involvement in prize-based research programs; 2) expanding involvement of undergraduates in the proposed research through targeted projects and collaboration with graduate students; 3) enhancing graduate education through the use of real-life projects and raw, unfinished research. We have already begun to work towards these goals and describe some of our successes.

Principal Investigator: Ari Trachtenberg
Sponsor: National Science Foundation