Summary

Various synchronization protocols and technologies like Hotsync (Fastsync and Slowsync), Intellisync, SyncML and CPISync are suitable for specific classes of synchronization problems because they scale only with certain parameters and not with others. For example, the total time is determined by the communication complexity and corresponding time for sending synchronization data over the network connecting the synchronizing devices as well as the amount of time required for any computations while determining the differences. The memory used on each device to maintain synchronization information is also taken into consideration as one of the scalability criteria, as is the number of devices that can synchronize among themselves (the size of the network). Finally, the robustness of the protocol - whether it is centralized or peer-to-peer is another scalability criteria. Fastsync only works for two device networks while Slowsync does not scale with large data sets on the synchronizing hosts. Similarly Intellisync depends entirely on a central server for synchronization instead of a peer-to-peer approach which makes it prone to central point of failure problems. SyncML is not scalable with a large number of devices on the network because it requires each device to maintain synchronization information for each record with respect to every other device in the network. CPISync alleviates all these problems, but is expensive when there are many differences between the synchronizing hosts due to the computational complexity being cubic in the number of differences between the synchronizing hosts. The CPISync algorithm has been implemented in a PC-PDA synchronization setting and has been shown to perform better than Slowsync for the case when the number of differences between the synchronizing PC and PDA is not overly large, as is the typical case in successive PC-PDA synchronizations. Since CPISync based Synchronization is independent of which particular device the PDA synchronized to the last time, the same algorithm can be used repeatedly while synchronizing a PDA with different devices, unlike Fastsync. On the memory front, the device has to maintain synchronization information which is of the order of $O(\overline{m})$, $\overline{m}$ being the upper bound on the number of differences between the two synchronizing hosts. The same information can be reused to synchronize with any number of devices. The CPISync algorithm is thus able to solve the synchronization problem efficiently for many cases of synchronization, although as mentioned earlier, it will not work well for a large number of differences between synchronizing hosts. A more intelligent mechanism of choosing a synchronization protocol depending on the specifics of the data being synchronized will solve the synchronization protocol most efficiently. For example, if the two devices synchronize successively then Fastsync may be employed, otherwise CPISync or Slowsync may be chosen depending upon the number of differences between the two devices.