Efficient Data Synchronization - 06/25/2010

Jiaxi Jin

Abstract: The efficiency of data synchronization has direct impact on the time cost of data-exchange protocol, such as PDA-PC synchronization and maintenance of eouting ta ble. Instead of naively transfer the wholesale of entire data set, we implemented the Characteristic Polynomial Synchronization algorithm (CPISync) which nearly reaches the optimal bound, to transfer only the difference between the sets(without knowing it in advance). The idea to apply the CPISync algorithm to PDAs was first covered in the paper by Ari Trachtenberg, David Starobinski, and Sachin Agarwal, ”Fast PDA Synchronization using Characteristic Polynomial Interpolation" in the Proceedings of INFOCOM 2002, pp.1510-1519, June 2002.

Based on the work of Jie, who worked in Nislab last year. I implemented a generalized CPI method called Probablistic CPI, which could guess the number of difference between two sets and automatically run CPI algorithm on the synchronization. In theory, without knowing the symmetric difference M of two sets, with Probablistic CPI the synchronization can be done in log(M) attempts.

I upgrade the agents of different CPI method(i.e. Basic CPI, Prob CPI) which can handle only sets of strings to make them capable of synchronizing sets of pinctures as well. And there will be a demo of doing so at the end of this talk.

-- JiaxiJin - 25 Jun 2010

• Pres100622_Jin.pptx: PPT for the presentation