Boston University  Engineering Home  Electrical & Computer Engineering  Contact us 

Characteristic polynomial interpolation for fast data synchronization Available in postscript(5.7M) or pdf(372k) Many Current PDA (Personal Digital Assistant) architectures use
an algorithm known as slow sync for the synchronization of a PDA with a
PC. This algorithm requires a transfer of all the PDA data to the PC in
order to determine the differing records between their databases. This
approach turns out to be particularly inefficient, in terms of bandwidth
usage and latency, as the actual number of differing entries is typically
much smaller that the total number of records stored on the PDA. We
have proposed, analyzed and actually implemented a novel PDA
synchronization scheme termed The basic approach taken by CPIsync is a hashing of the data into
a certain type of polynomial known as characteristic polynomial. Both the
PDA and the PC maintain their own polynomial. When synchronizing, the PDA
sends to the PC evaluations of its polynomial at a number of random
points. This number must exceed the number of differing entries. These
evaluations suffice for the PC to determine all the differences, through a
computational procedure known as interpolation. Our implementation shows
that the computational complexity of CPIsync is affordable in most
reasonable scenarios, and the time taken to perform synchronization is
generally much smaller than with slow sync. The CPIsync scheme thus
carries the potential for a tremendous performance improvement over
current PDA synchronization Read a related paper S. Agarwal, D. Starobinski, and A. Trachtenberg, On the Scalability of Data Synchronization Protocols for PDAs and Mobile Devices, special issue IEEE Network Magazine: Scalability in Communication Networks, to appear July/August. Available in ps (5.5M) or pdf (973k).
Lab of Networking and Information Systems Room 413 Photonics Building 8 St Mary's Street, Boston MA 02215
Web site created by Sachin Agarwal (ska@bu.edu)
