publication . Part of book or chapter of book . 2013

from rational number reconstruction to set reconciliation and file synchronization

Amarilli, Antoine; Ben Hamouda, Fabrice; Bourse, Florian; Morisset, Robin; Naccache, David; Rauzy, Pablo;
Open Access
  • Published: 01 Jan 2013
  • Publisher: Springer Berlin Heidelberg
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...
free text keywords: Synchronizing, Overhead (computing), File synchronization, Theoretical computer science, Rational number, Computer science, Software, business.industry, business, Chinese remainder theorem, Distributed computing, Hash function, Synchronization
Related Organizations
Download fromView all 2 versions
Part of book or chapter of book
Provider: UnpayWall
Part of book or chapter of book . 2013
Provider: ZENODO
Part of book or chapter of book
Provider: Crossref
Powered by OpenAIRE Research Graph
Any information missing or wrong?Report an Issue