Scope of this Thesis

There are two basic components to this thesis. Chapter $2$ of this thesis, which is based on [12], discusses some of the contemporary synchronization technologies and compares their performance with respect to utilization of bandwidth, processing and memory. We have discussed Hotsync (the synchronization scheme used in Palm PDAs), Pumatech's Intellisync and the industry wide SyncML initiative. In addition, there is a brief description of the CPISync algorithm in Chapter $2$ to compare it with the above protocols. The survey brings out some of the scalability limitations of each these protocols. In the second part, we discuss CPISync, which is a synchronization solution based on a set reconciliation problem's solution. Chapter $3$ describes the CPISync algorithm in detail and application of CPISync algorithm for PDA synchronization. Some of this work has appeared in [13]. This algorithm was first proposed in  [14] in which the authors had provided preliminary results that suggested that the algorithm could be useful for data synchronization among databases with a limited number of differences between them. The major contribution of our research is transcribing the algorithm from a purely mathematical idea to an actual implementation on a mobile device (Palm PDA) and a PC. The algorithm was studied and analyzed first. A substantial part of the research was the partitioning of the algorithm into two asymmetric parts (in terms of computational complexity) corresponding to the asymmetric computational capabilities of a PDA and a PC. The less computationally intensive part was coded into the slower Palm IIIxe PDA running the Palm Operating System while the more intensive part of the algorithm was coded into the faster PC. The design specification took into consideration subtleties like fitting all the calculations to the word size of the Palm processor architecture to speed up the computation on the Palm PDA. The Palm PDA has a word length of 16 bits and methods to limit all mathematical operations within this limit were put in place. We also implemented a more advanced $512$ bit data version of CPISync in anticipation of future applications of the algorithm not necessarily related to PDAs. In all these implementations, we tried to reduce the constants associated with the cubic complexities of some of the mathematical operations of CPISync. In addition to all this, issues of communication between the Palm PDA and the PC were sorted out and put in place for a real implementation on the PC-PDA synchronization system. Methods and tools to quantify and compare the performance of CPISync with the Hotsync protocol (the commercially used synchronization protocol in Palm PDAs) were developed and deployed. Results from this analysis were used to mathematically model an intelligent mechanism to switch between CPISync and Hotsync on the specific requirements of a synchronization. These results were also used to design a more sophisticated version of CPISync which could synchronize without a prior bound on the number of differences between the databases. This was the `probabilistic' algorithm first proposed in [14]. The more sophisticated version was also implemented on the PC-PDA system. In related work, our implementation of CPISync is being used as the underlying synchronization routine in the development of a real memo application on the Palm PDA platform. The memo application uses CPISync to synchronize with PCs, as described in [15]. The encouraging results of the utility of CPISync in fast PDA synchronization lead us to apply the algorithm to the more general problem of Network Synchronization. We concentrated on the resource discovery problem in networks in particular. To this end, we picked upon the `Name-Dropper' network resource discovery algorithm [10]. We built a simple simulator to compare the performance of the Name-Dropper using CPISync and wholesale data transfer (like Slowsync) separately for synchronization. For completeness, we contrasted these results with flooding, a commonly used resource discovery algorithm. This project brings forward some interesting results and we hope that more work in this area will be an interesting extension to the application of CPISync. Finally there is a conclusion at the end of this thesis, which includes directions for future work, including the preliminary work on the application of CPISync to the network resource discovery problem.