System Model

The PC-PDA model used a Palm IIIxe with a 16 bit Motorola Dragon ball processor [29] and 8MB of RAM. The palm was synchronized with a Pentium III class machine with $512$ MB of RAM. We used a serial RS-232 link operating at $115 kbps$ as the link between the PDA and the PC. Our specific implementation emulates a memo pad implementation. As data is entered into the palm, evaluations of the characteristic polynomial (described in the previous section) are updated at designated sample points. Upon a request for synchronization, the Palm sends $\overline{m}$ of these evaluations to the PC, corresponding to the differences between the data and the two machines. The desktop compares these evaluations to its own evaluations and determines the differences between the two machines, as described in section 3.2 on page . We do not address issues about which specific data to keep at the end of the synchronization cycle in case of conflicts, but several techniques from database literature explained in [30] are possible candidates for conflict resolution.

Figure 3.4: A sample script to illustrate an experiment on the PC-PDA system

Finite field arithmetic was performed with Victor Shoup's Number Theory Library and data transferred between the PDA and the PC in pdb (Palm database) format. This data was converted to text format using [31]. This data is converted to input suitable to the CPISync system on the PC using a separate Java language based string parser. Figure 3.4 shows a sample script of an experimental run of our system and explains how the PC-PDA system is setup. Our model uses the Hotsync middleware of the Palm operating system to transfer data as pdb files. We have used the default conduit provided in the Palm OS API [32] for this purpose. In the experiments we performed, the number of differences between the data sets held on the PC and the PDA varied from 0 to about $1200$ and the size of the data sets varied from $100$ to $10000$. Since it was not practical to manually introduce these ranges of data and differences, we implemented an automatic data generator on the PC and the PDA. The program on the PDA was called Reconciliation Genie. This program took two inputs - the size of the database and the number of differences to be introduced. Instead of actually generating this data set, genie just calculated the characteristic polynomial of the data set elements (they were serially ordered). The range of the data elements could be between $8188$ and $24561$ in the finite field $F_{32749}$. This particular choice is because out of the total $32749$ elements in the finite field, the first and last quarter are reserved for sample points (as was explained in section 3.2. A complementary program on the PC took the same inputs - the size of the database and the number of differences to be introduced and constructed a database accordingly. So for testing purposes, we simulated a situation wherein we `knew' the number of differences so as to set up the desired synchronization set size and difference parameters. It is important to note here that the CPISync system on the PDA and the PC itself was not a simulation.