Subspace synchronization: A network-coding approach to object reconciliation
Vitaly Skachek, Michael Rabbat · 2014
Assume that two users possess two different subspaces of an ambient linear space. We show that the problem of synchronization of such vector spaces can be easily solved by an efficient algorithm. By building on this observation, we propose an algorithm for synchronization of two collections of binary files of length n each, stored in the cloud in a distributed manner. By further employing techniques akin to network coding, we propose a more efficient file synchronization algorithm that has communication complexity O(d · n) bits and computational complexity O(k2· n) operations, where k is the total number of files and d is the number of files that differ. The algorithm successfully reconciles two sets of files in 3 communication rounds with high probability.