Reconciliation puzzles
Vikas Singh Chauhan, Ari Trachtenberg · 2005
We consider the problem of exchanging two similar strings held by different hosts with a minimum amount of communication. We reduce the problem of string reconciliation to a problem of multi-set reconciliation, for which nearly optimal solutions exist. Our approach involves transforming a string into a multi-set of substrings, which are reconciled efficiently and then put back together on a remote host using recent graph-theoretic results. We present an analysis of our algorithm to show that its communication complexity compares favorably to two existing methods for string reconciliation.