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 Characteristic Polynomial Interpolation-based Synchronization (CPIsync), that relies on recent information-theoretic research results. The most salient property of this scheme is that the amount of communication needed for synchronizing the databases of the PDA and the PC relates only to their mutual differences.

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 protocols.

Read a related paper