Boston University
Scalable string reconciliation by recursive content-dependent shingling
Abstract
dc:description.abstractWe 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.
Degree
thesis:*- Name thesis:degree_name
- Master of Science
- Level thesis:degree_level
- masters
- Discipline thesis:degree_discipline
- Electrical & Computer Engineering
- Grantor
- Boston University
- Year dc:date.issued
- 2019
Author and committee
dc:creator, dc:contributor.*- Author dc:creator
-
- Song, Bowen
- Advisor dc:contributor.advisor
-
- Trachtenberg, Ari
Subjects
dc:subject × 1Rights
dc:rights- Statement dc:rights
-
- Attribution-ShareAlike 4.0 International
- Licence dc:rights.uri
- Language dc:language.iso
- en_US
Identifiers
dc:identifier.*- Handle dc:identifier.uri
- https://hdl.handle.net/2144/36028