Abstract
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 software rsync. It appears that btrsync transmits much less data than rsync, at the expense of a relatively modest computational overhead.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abdalla, M., Ben Hamouda, F., Pointcheval, D.: Tighter Reductions for Forward-Secure Signature Schemes. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 292–311. Springer, Heidelberg (2013)
Amarilli, A., Ben Hamouda, F., Bourse, F., Morisset, R., Naccache, D., Rauzy, P.: From Rational Number Reconstruction to Set Reconciliation and File Synchronization. Full version available from the authors’ webpage
Burnikel, C., Ziegler, J., Stadtwald, I.: Fast Recursive Division, Tech. Rep., MPI-I-98-1-022, MPI Informatik Saarbrucken (1998)
Byers, J., Considine, J., Mitzenmacher, M., Rost, S.: Informed Content Delivery Across Adaptive Overlay Networks. ACM SIGCOMM Computer Communication Review 32(4), 47–60 (2002)
Coron, J.-S., Naccache, D.: Security Analysis of the Gennaro-Halevi-Rabin Signature Scheme. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 91–101. Springer, Heidelberg (2000)
Eppstein, D., Goodrich, M., Uyeda, F., Varghese, G.: What’s the Difference?: Efficient Set Reconciliation Without Prior Context. ACM SIGCOMM Computer Communication Review 41, 218–229 (2011)
Fouque, P.A., Stern, J., Wackers, J.G.: Cryptocomputing With Rationals. In: Blaze, M. (ed.) FC 2002. LNCS, vol. 2357, pp. 136–146. Springer, Heidelberg (2003)
Hohenberger, S., Waters, B.: Short and Stateless Signatures from the RSA Assumption. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 654–670. Springer, Heidelberg (2009)
Minsky, Y., Trachtenberg, A.: Practical Set Reconciliation, Tech. Rep., Department of Electrical and Computer Engineering, Boston University, Technical Report BU-ECE-2002-01, 2002, a full version can be, downloaded from http://ipsit.bu.edu/documents/BUTR2002-01.ps
Minsky, Y., Trachtenberg, A., Zippel, R.: Set Reconciliation With Nearly Optimal Communication Complexity. IEEE Transactions on Information Theory 49(9), 2213–2218 (2003)
Pan, V., Wang, X.: On Rational Number Reconstruction and Approximation. SIAM Journal on Computing 33(2), 502–503 (2004)
Schönhage, A., Strassen, V.: Schnelle Multiplikation großer Zahlen. Computing 7(3), 281–292 (1971)
Tridgell, A.: Efficient Algorithms for Sorting and Synchronization, Ph.D. thesis, The Australian National University (1999)
Vallée, B.: Gauss’ Algorithm Revisited. Journal of Algorithms 12(4), 556–572 (1991)
Wang, X., Pan, V.: Acceleration of Euclidean Algorithm and Rational Number Reconstruction. SIAM Journal on Computing 32(2), 548–556 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Amarilli, A., Ben Hamouda, F., Bourse, F., Morisset, R., Naccache, D., Rauzy, P. (2013). From Rational Number Reconstruction to Set Reconciliation and File Synchronization. In: Palamidessi, C., Ryan, M.D. (eds) Trustworthy Global Computing. TGC 2012. Lecture Notes in Computer Science, vol 8191. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-41157-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-642-41157-1_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-41156-4
Online ISBN: 978-3-642-41157-1
eBook Packages: Computer ScienceComputer Science (R0)