PDA Synchronization

Personal digital assistants or PDAs are periodically linked up to computers in order to synchronize data being held on the PDA and the data held by complementary applications on the computer. A secondary benefit of periodic synchronization is that it serves as a backup mechanism. Typical application data that needs to be synchronized includes address books, memo pads, to-do lists, email clients, schedule planners and off-line internet and web information (like avantgo [27]). Information in these applications is modified on the PDA and/or the PC independently. The more often synchronization is done, more current is the data being held on the PDA and the PC. A natural result of frequent synchronization is that the amount of `new' information between two successive synchronizations is very small compared to the total amount of information in the databases of the PDA and the PC. In this chapter we first introduce CPISync (characteristic polynomial interpolation based synchronization) in Section 3.1 that is based on a set reconciliation algorithm first proposed in [14]. We then describe two variants of the original algorithm, namely Deterministic CPISync and Probabilistic CPISync in Sections 3.2 and 3.3. The algorithms' theory as well as implementation and results are described in these sections. The CPISync algorithm is suitable for application in PDA synchronization because it makes the communication and time complexity of synchronization a function of the differences between two databases being compared and not the size of the databases themselves. In this chapter we first discuss the CPISync algorithm and then go on to discuss its application in the PC-PDA synchronization system. Towards the end of the chapter we discuss the our results of the CPISync PC-PDA synchronization as compared to Slowsync, discussed in Section 2.2.1.