Efficient point-to-multipoint data reconciliation

Abstract

Efficient reconciliation of different versions of a target file or dataset can be facilitated using a hash hierarchy of a master version of the dataset. Each level of the hash hierarchy has hashes of blocks of the master version that may be sub-blocks of the hashes in the level above. The top level of the hash hierarchy, having the hashes of the largest blocks of the master, may be transmitted on a first communication channel, possibly a one-way or broadcast communication channel. Streams of encodings of each lower level of the hash hierarchy may be transmitted on respective communication channels. The encodings for a level of the hierarchy may be combinations, such as random linear combinations, of the hashes of that level. A receiver with a target dataset can receive the top level hashes from the first channel and use them to determine which lower hashes are needed to identify parts of the master missing from the target. The encodings can be used to help obtain needed lower level hashes that can be used to more finely identify missing parts. Different receivers may not have to wait for a particular piece of information about the master. Rather, any received information (e.g. encoding) about the master will most likely allow any receiver to advance its understanding of the master dataset. Receivers will usually not have to wait for delivery of a particular hash in the hierarchy.

1 . A system comprising a receiving device configured for decoding at least one received encoding of a remote portion of a remote hash hierarchy of a remote dataset, wherein the at least one received encoding is a random linear combination of block hashes of the remote portion produced by crossing a vector of random coefficients with a matrix of the block hashes. 
     
     
         2 . The system of  claim 1  further comprising the receiving device further configured for reconstructing the remote dataset based at least in part on received block hashes of a top level of the remote hash hierarchy. 
     
     
         3 . The system of  claim 1  further comprising the receiving device further configured for reconstructing the remote dataset based at least in part on the decoded encoding. 
     
     
         4 . The system of  claim 1  further comprising the receiving device further configured for reconstructing the dataset based at least in part on received encodings of the remote dataset. 
     
     
         5 . The system of  claim 1  further comprising the receiving device further configured for reconstructing the remote dataset based at least in part on a received seed value configured to enable the receiving device to reproduce the vector of random coefficients. 
     
     
         6 . The system of  claim 1  further comprising the receiving device further configured for reconstructing the remote dataset based at least in part on received data associated with each of various levels of the remote hash hierarchy via a communication channel unique to the each of the various levels. 
     
     
         7 . The system of  claim 1  wherein there is a mathematical relationship between hashes of neighboring levels of the remote hash hierarchy. 
     
     
         8 . A method comprising decoding, by a receiving device, at least one received encoding of a portion of a hash hierarchy of a dataset, wherein the at least one received encoding is a random linear combination of block hashes of the portion produced by crossing a vector of random coefficients with a matrix of the block hashes. 
     
     
         9 . The method of  claim 8  reconstructing the remote dataset based at least in part on received block hashes of a top level of the remote hash hierarchy. 
     
     
         10 . The method of  claim 8  reconstructing the remote dataset based at least in part on the decoded encoding. 
     
     
         11 . The method of  claim 8  reconstructing the dataset based at least in part on received encodings of the remote dataset. 
     
     
         12 . The method of  claim 8  reconstructing the remote dataset based at least in part on a received seed value configured to enable the receiving device to reproduce the vector of random coefficients. 
     
     
         13 . The method of  claim 8  reconstructing the remote dataset based at least in part on received data associated with each of various levels of the remote hash hierarchy via a communication channel unique to the each of the various levels. 
     
     
         14 . The method of  claim 8  wherein there is a mathematical relationship between hashes of neighboring levels of the remote hash hierarchy. 
     
     
         15 . At least one computer-readable media storing computer-executable instructions that, when executed by a receiving device, cause the receiving device to perform a method comprising decoding at least one received encoding of a portion of a hash hierarchy of a dataset, wherein the at least one received encoding is a random linear combination of block hashes of the portion produced by crossing a vector of random coefficients with a matrix of the block hashes. 
     
     
         16 . The at least one computer-readable media of  claim 15 , the method further comprising reconstructing the remote dataset based at least in part on received block hashes of a top level of the remote hash hierarchy. 
     
     
         17 . The at least one computer-readable media of  claim 15 , the method further comprising reconstructing the remote dataset based at least in part on the decoded encoding and on received encodings of the remote dataset. 
     
     
         18 . The at least one computer-readable media of  claim 15 , the method further comprising reconstructing the remote dataset based at least in part on a received seed value configured to enable the receiving device to reproduce the vector of random coefficients. 
     
     
         19 . The at least one computer-readable media of  claim 15 , the method further comprising reconstructing the remote dataset based at least in part on received data associated with each of various levels of the remote hash hierarchy via a communication channel unique to the each of the various levels. 
     
     
         20 . The at least one computer-readable media of  claim 15  wherein there is a mathematical relationship between hashes of neighboring levels of the remote hash hierarchy.