Scalable string reconciliation by recursive content-dependent shingling
Files
Main thesis
View Scalable String Reconciliation Presentation.pdf
Date
2019
DOI
Authors
Song, Bowen
Version
Embargo Date
2019-12-03,2019-12-03
OA Version
Citation
Abstract
We consider the problem of reconciling similar strings in a distributed system. Specifically, we are interested in performing this reconciliation in an efficient manner, minimizing the communication cost. Our problem applies to several types of large-scale distributed networks, file synchronization utilities, and any system that manages the consistency of string encoded ordered data. We present the novel Recursive Content-Dependent Shingling (RCDS) protocol that can handle large strings and has the communication complexity that scales with the edit distance between the reconciling strings. Also, we provide analysis, experimental results, and comparisons to existing synchronization software such as the Rsync utility with an implementation of our protocol.
Description
License
Attribution-ShareAlike 4.0 International