Scalable String Reconciliation by Recursive Content-Dependent Shingling
| Autor: | Ari Trachtenberg, Bowen Song |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2019 |
| Předmět: |
FOS: Computer and information sciences
Theoretical computer science Computer science Information Theory (cs.IT) Computer Science - Information Theory String (computer science) 0102 computer and information sciences 02 engineering and technology 01 natural sciences 010201 computation theory & mathematics 020204 information systems Scalability Synchronization (computer science) 0202 electrical engineering electronic engineering information engineering Edit distance Shingling File synchronization Communication complexity Block (data storage) |
| Zdroj: | Allerton |
| Popis: | We consider the problem of reconciling similar, but remote, strings with minimum communication complexity. This "string reconciliation" problem is a fundamental building block for a variety of networking applications, including those that maintain large-scale distributed networks and perform remote file synchronization. We present the novel Recursive Content-Dependent Shingling (RCDS) protocol that is computationally practical for large strings and scales linearly with the edit distance between the remote strings. We provide comparisons to the performance of Rsync, one of the most popular file synchronization tools in active use. Our experiments show that, with minimal engineering, RCDS outperforms the heavily optimized Rsync in reconciling release revisions for about 51% of the 5000 top starred git repositories on GitHub. The improvement is particularly evident for repositories that see frequent, but small, updates. 8 pages, 7 figures, 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton) |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|