ProbSync Performance - An Alternative to CPISync?

  Figure 4 shows the performance of a variant of the CPISync algorithm known as ProbSync. Rather than have a strict upper bound on the number of differences that it can synchronize between (as CPISync does), ProbSync starts with a small upper bound, but if unable to synchronize using that bound, it will increase the bound and use more evaluations. The upper bound on the number of differences is now limited only to the number of evaluations that the PalmPilot makes available to the PC running ProbSync. In addition, since ProbSync is simply running CPISync until it manages to confirm that it has used a sufficient number of polynomials (it can confirm this with a certain probability of assuredness, hence ProbSync) ProbSync usually takes less time than straight CPISync. This is because CPISync takes computation cubic in the size of the upper bound on the number of differences, so for small numbers of differences, ProbSync can capitalize on a much lower synchronization time. Our prototype system is designed to switch seamlessly between the two methods of synchronization. All other blocks of time in the figure are unaffected by this change in the system.