publication . Part of book or chapter of book . 2013

From Rational Number Reconstruction to Set Reconciliation and File Synchronization

Antoine Amarilli; Fabrice Ben Hamouda; Florian Bourse; Robin Morisset; David Naccache; Pablo Rauzy;
Open Access
  • Published: 04 Sep 2013
This work revisits set reconciliation, the problem of synchronizing two multisets of fixed-size values while minimizing transmission complexity. We propose a new number-theoretic reconciliation protocol called Divide and Factor (D&F;) that achieves optimal asymptotic transmission complexity — as do previously known alternative algorithms. We analyze the computational complexities of various D&F; variants, study the problem of synchronizing sets of variable-size files using hash functions and apply D&F; to synchronize file hierarchies taking file locations into account. We describe btrsync, our open-source D&F; implementation, and benchmark it against the popular...
Persistent Identifiers
free text keywords: Hash function, Theoretical computer science, File synchronization, Synchronization, Computer science, Overhead (computing), Chinese remainder theorem, Software, business.industry, business, Rational number, Synchronizing
Download fromView all 2 versions
Open Access
Part of book or chapter of book
Provider: UnpayWall
Open Access
Part of book or chapter of book . 2013
Provider: ZENODO
Part of book or chapter of book . 2013
Provider: Crossref
Any information missing or wrong?Report an Issue