Scalable String Reconciliation by Recursive Content-Dependent Shingling

arXiv1910.00536MaRDI QIDQ6326344

Ari Trachtenberg, Bowen Song

Publication date: 1 October 2019

Abstract: 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.

Has companion code repository: https://github.com/String-Reconciliation-Ditributed-System/RCDS_GO

This page was built for publication: Scalable String Reconciliation by Recursive Content-Dependent Shingling

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326344)