An Exploration of Two-Party Reconciliation Problems

Abstract

This thesis explores various two-party reconciliation problems from a theoretical perspective. We define a reconciliation problem to be one in which Alice and Bob each have some data, and their data is in some problem specific way similar. We wish for them to communicate efficiently so that Bob can recover Alice's data, or something close to it. Alice could transmit her data directly to Bob but we wish to exploit the similarity between their data to use fewer bits of communication. These problems have immediate applications to various forms of synchronization in distributed systems. This classification captures set reconciliation, document exchange, and robust set reconciliation. We present new protocols for document exchange and robust set reconciliation, improving upon the state of the art. We also introduce and study several new reconciliation problems, such as reconciling sets of sets, undirected graphs, and directories. We develop efficient protocols for all of these problems. Along the way, we develop new analysis of error propagation in peeling processes and a communication efficient process for a form of noisy binary search in trees, both of which may be of independent interest.