Efficient PDA synchronization

Modern personal digital assistant (PDA) architectures often utilize a wholesale data transfer protocol known as "slow sync" for synchronizing PDAs with personal computers (PCs). This approach is markedly inefficient with respect to bandwidth usage, latency, and energy consumption since the PDA and PC typically share many common records. We propose, analyze, and implement a novel PDA synchronization scheme (CPIsync) predicated upon previous information-theoretic research. The salient property of this scheme is that its communication complexity depends on the number of differences between the PDA and PC, and is essentially independent of the overall number of records. Moreover, our implementation shows that the computational complexity and energy consumption of CPIsync is practical and that the-overall latency is typically much smaller than that of slow sync or alternative synchronization approaches based on Bloom (1970) filters. Thus, CPIsync has potential for significantly improving synchronization protocols for PDAs and, more generally, for heterogeneous networks of many machines.