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 sending device configured for generating at least one encoding of a portion of a hash hierarchy of a dataset, wherein the generated at least one 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. 
     
     
         2 . The system of  claim 1  further comprising the sending device further configured for transmitting block hashes of a top level of the hash hierarchy. 
     
     
         3 . The system of  claim 1  further comprising the sending device further configured for transmitting the at least one encoding of the portion of the hash hierarchy of the dataset. 
     
     
         4 . The system of  claim 1  further comprising the sending device further configured for transmitting encodings of the dataset. 
     
     
         5 . The system of  claim 1  further comprising the sending device further configured for transmitting a seed value configured to enable a receiver to reproduce the vector of random coefficients. 
     
     
         6 . The system of  claim 1  further comprising the sending device further configured for transmitting data associated with each level of the hash hierarchy via a communication channel unique to the each level. 
     
     
         7 . The system of  claim 1  wherein there is a mathematical relationship between hashes of neighboring levels of the hash hierarchy. 
     
     
         8 . A method comprising generating, by a sending device, at least one encoding of a portion of a hash hierarchy of a dataset, wherein the generated at least one 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  further comprising transmitting block hashes of a top level of the hash hierarchy. 
     
     
         10 . The method of  claim 8  further comprising transmitting the at least one encoding of the portion of the hash hierarchy of the dataset. 
     
     
         11 . The method of  claim 8  further comprising transmitting encodings of the dataset. 
     
     
         12 . The method of  claim 8  further comprising transmitting a seed value configured to enable a receiver to reproduce the vector of random coefficients. 
     
     
         13 . The method of  claim 8  further comprising transmitting data associated with each level of the hash hierarchy via a communication channel unique to the each level. 
     
     
         14 . The method of  claim 8  wherein there is a mathematical relationship between hashes of neighboring levels of the hash hierarchy. 
     
     
         15 . At least one computer-storage media storing computer-executable instructions that, when executed by a sending device, cause the sending device to perform a method comprising generating at least one encoding of a portion of a hash hierarchy of a dataset, wherein the generated at least one 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-storage media of  claim 8 , the method further comprising:
 transmitting block hashes of a top level of the hash hierarchy; and   transmitting encodings of the dataset.   
     
     
         17 . The at least one computer-storage media of  claim 8 , the method further comprising transmitting the at least one encoding of the portion of the hash hierarchy of the dataset. 
     
     
         18 . The at least one computer-storage media of  claim 8 , the method further comprising transmitting data associated with each level of the hash hierarchy via a communication channel unique to the each level. 
     
     
         19 . The at least one computer-storage media of  claim 8 , the method further comprising transmitting a seed value configured to enable a receiver to reproduce the vector of random coefficients. 
     
     
         20 . The at least one computer-storage media of  claim 8  wherein there is a mathematical relationship between hashes of neighboring levels of the hash hierarchy.