System Model

From an end-user perspective, the most important metric of usability of any synchronization protocol is the latency in the synchronization process. We therefore consider optimizing the latency with the view of minimizing it. We thus propose a scheme whose completion time is at worst a constant $\alpha$ times larger than the time needed to synchronize the two hosts when the number of differences is know a priori (using the Deterministic scheme discussed in 3.2 on page ). This probabilistic scheme retains one of the essential properties of its deterministic counterpart: the synchronization latency depends only on the number of differences and not on the total size of the host data sets. We prove that $\alpha = 4$ is the optimal bound for this scheme and show how to achieve it.

Figure 3.9: A model of the approach used to optimize the latency of synchronization when no bound is known on the number of differences between data sets.

Our approach to this optimization relies in part on the data graphed in Figure 2.7. We fit our data to a polynomial regression that interpolates the latency of CPISync as a function of the number of differences $m$ between the two hosts as was shown in Table3.2. Since an exact value for $m$ is not known at the start, the PDA and PC start with an initial guess $\overline{m}$ for an upper bound on $m$. In Figure 3.9, this initial guess corresponds to a value $\overline{m}_1$, which corresponds to a verification time of $t_1 = 3.65$ seconds. If verification fails this guess, we update our bound to the value $\overline{m}_2$ that corresponds to a verification time that is $\delta$ times larger than for $\overline{m_1}$ differences(i.e. $t_2 = \delta\cdot t_1$). In the case of Figure 3.9, $\delta = 2$ giving $\overline{m} = 151$ and $t_2 \approx 7.29$ seconds. At each iteration we guess the bound $\overline{m}_i$ such that $t_i = \delta\cdot t_{i-1}$. We continue until verification succeeds for some guessed bound $\overline{m_n}$ requiring time $t_n = \delta^{n-1}\cdot t_1$ [13]: Theorem 1 The latency-optimizing probabilistic scheme takes at most $\alpha(\delta) = \frac{\delta^2}{\delta-1}$ times longer than a deterministic scheme with an a priori knowledge of the actual number of differences. Proof: Denote by $T^*(m)$ the synchronization latency when $m$ is know a priori, and by $T(m)$ the synchronization latency required by this probabilistic scheme. Furthermore, denote by $t_i$ the time needed for the $i$-th verification round in which $\overline{m}_i$ differences are guessed between the two hosts. Suppose that a correct upper bound, $\overline{m}_n \geq m$, is observed first at the $n$-th iteration, for $n > 1$. The total synchronization time required for the probabilistic scheme is then simply the sum of the geometric progression

$$T(m) = t_1 + \hdots + t_n = t_1 + \delta\cdot t_1 + \hdots + \delta^{n-1}\cdot t_1 = \frac{\delta^n - 1}{\delta - 1}\cdot t_1$$ (3.5)

Note that $T^*(m) \geq t_{n-1} = \delta{n-2}\cdot t_1$, since $\overline{m}_n$ is assumed to be the first correct upper bound $m$. We this obtain

$$\frac{T}{T^*} \geq \frac{\delta^n-1}{(\delta-1)\delta^{n-2}}, n>1.$$ (3.6)

It is easy to check that the right hand side of (3.6) is maximized when $n \to \infty$, meaning that $T/T^* \geq \delta^2/(\delta-1)$. By examining the derivative of $\alpha(\delta)$ with respect to $\delta$, one finds that this function attains a minimum value at $\delta = 2$, leading to an optimal ratio of $\alpha = 4$. Thus, the best policy for this scheme is to double the verification time at each iteration.

Figure 3.10: A comparison of the Probabilistic scheme with no known upper bound $\overline{m}$ to the deterministic scheme with a given value of $m$.