BOSTON UNIVERSITY

COLLEGE OF ENGINEERING

Thesis

DATA SYNCHRONIZATION IN

MOBILE AND DISTRIBUTED NETWORKS

by

SACHIN KUMAR AGARWAL

B.Tech., Regional Engineering College, Warangal, India

May 2000

Submitted in partial fulfillment of the

requirements for the degree of

Master of Science

2002

Approved by

First Reader 


Ari Trachtenberg


Assistant Professor of Electrical and Computer Engineering


Boston University










Second Reader		


David Starobinski


Assistant Professor of Electrical and Computer  Engineering


Boston University

Acknowledgments

I would like to first acknowledge my advisor, Prof. Ari Trachtenberg for his constant support and guidance through the research and writing that constitute this thesis. It is a great understatement to say that this work would not have been possible without his help. I would also like to extend my gratitude to Prof. David Starobinski for his constructive inputs in the form of discussions and new ideas to this work. I would also like to acknowledge my readers, Prof. David Starobinski and Prof. Jeffrey Carruthers for their comments and helpful discussions. I would like to thank my family who has been extremely supportive throughout the time I've been working on my thesis. My father and mother for being there when I needed them and my brother for his encouragement. Finally I would like to thank my lab cohorts for their help and tolerance during the thesis process.

DATA SYNCHRONIZATION IN MOBILE AND DISTRIBUTED NETWORKS

SACHIN KUMAR AGARWAL

Boston University College of Engineering, 2002
Major Professor: Ari Trachtenberg, Assistant Professor of Electrical and Computer Engineering

Abstract

The rapid increase in networked mobile devices has made it important to develop scalable data synchronization protocols that will periodically synchronize data held on these devices. Synchronization seeks to maintain consistency in data that is being changed on each of these mobile hosts independently. This has to be achieved within practical constraints on overhead that limit the amount of data exchanged during synchronization, the amount of memory used to store synchronization data, and the computation involved while running the synchronization protocol. In addition, any synchronization protocol should scale with the number of devices that might be synchronized with each other and should be resilient to failure, given the ad-hoc nature of mobile networks. We study some of the representative synchronization protocols in use today and then compare them to characteristic polynomial interpolation synchronization (CPISync), a more mathematical approach to synchronization implemented by us on a PC-PDA synchronization system. Two devices synchronizing using CPISync exchange only $O(\overline{m})$ bits where $\overline{m}$ is the upper bound on the number of differences between the reconciling data sets of the devices. Thus, CPISync is well-suited for typical PC-PDA data synchronization scenarios where the number of changes (additions/deletions/modifications) to databases between two synchronizations is typically bounded by a small constant. When a good bound on $\overline{m}$ is not known a priori we show that an enhancement to the basic algorithm keeps CPISync time complexity within a small multiplicative factor of the case when $\overline{m}$ is known a priori. Our experiments show that CPISync scales well with growing data size, which is increasingly the case with newer mobile devices.