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.
Terms of Use
This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAACitable link to this page
http://nrs.harvard.edu/urn-3:HUL.InstRepos:39947174
Collections
- FAS Theses and Dissertations [7063]
Contact administrator regarding this item (to report mistakes or request changes)