Hotsync

Palm PDAs run the Palm Operating System that provides the Hotsync protocol to synchronize databases held on the PDA and the PC to which the PDA synchronizes. Hotsync operates in two modes, depending on the synchronization history of the PDA with the particular PC. A Fastsync occurs when the PDA synchronizes with the same PC its synchronized with the last time. In this case the PDA synchronizes by processing records based on the status flags of each record which indicate whether it has been modified, deleted, left untouched or is a new record. This method approaches the lower information theoretic bounds on the communication complexity because intuitively the amount of data to be sent across to synchronize is at least equal to the difference between the two data sets (provided we knew somehow which data was updated or was new in the hosts with respect to the other). A more rigorous information theoretic view of this concept is explained in [14] which suggests that the lower bound on the amount of information to be exchanged between hosts $A$ and host $B$ with $m$ differences between their reconciling data sets comprised of $b$ bit elements is given by

$$I_{trans} \gtrapprox b \cdot m - m \cdot log(m)$$ (2.1)

This problem of reconciling two hosts' data sets is formally known as the set reconciliation problem. Thus Fastsync is the `best option' for two devices that synchronize with only each other. However, Fastsync will not scale with the number of devices in the network because the PDA can remember status flags only with respect to one PC. A Slowsync occurs when the prime condition for Fastsync is not met - when the PDA is syncing with a PC different from the one to which the it synced the last time Hotsync was invoked. In this case the PDA transfers the entire database to the PC to be worked upon by comparison. As PDA storage space becomes bigger and databases become larger, the issue of increasing latency involved in transferring the entire database from the PDA to the PC for subsequent synchronization becomes increasingly important. Figure 2.3 shows the difference in the communication complexity of Slowsync and Fastsync. Here, a database of appointments held on a PC and PDA is being synchronized using Slowsync and Fastsync. In the former protocol the PDA transfers its entire database to the PC and then the PC determines how to synchronize the databases while in the latter only the records which have been modified or added since the last synchronization are sent to the PC by the PDA.

Figure 2.4: Difference between the two modes of the HotSync protocol. In Slowsync all data is transferred, while in Fastsync only modifications are sent.

Figure 2.5: Recent faster data transfer technologies like USB and Firewire have reduced data transfer times by orders of magnitudes, though the potential size of data that may be transferred to or from a PDA has also increased accordingly.

It may be argued that with the advent of faster connection technologies for connecting mobile devices to PCs and networks and with the increasingly fast wireless LANs at hand, Slowsync latency becomes a tractable bottle-neck. Figure 2.5 shows some of the more recent technologies used by mobile devices to transfer data to and from PCs and networks, with a few representative PDAs and their approximate data storage capabilities marked out for comparison. It is interesting to note that even the state-of-the-art Firewire (IEEE $1394$) [17] and USB [18] technologies are not able to solve the data transfer latency problem because of a corresponding increase in the amount of data being handled by newer devices. For example, a Palm Pilot (1MB storage) using a serial link to transfer its entire data to a PC (as is the case in Slow Sync) will take approximately the same order of time ($73$ seconds) as an Apple Ipod (5GB storage) using the Firewire $1394$b data transfer technology ($54$ seconds).