Reconciliation Puzzles - 02/21/2002

Vikas Chauhan

We address the problem of reconciling structured data, specifically strings between two hosts. We seek to leverage results from the CPISync algorithm to reconcile structured data with minimum communication. To reconcile two different strings, one would first break up both strings into multi-sets of pieces, and then reconcile these multi-sets using CPISync. Once the multi-sets are reconciled, each host knows what pieces the other host has and tries to decode these pieces into a string. This approach can be applied to data that has been organized in two-dimensions too (Image Reconciliation, for example). The emphasis of the talk will be on the decoding algorithm, on which we are still working.