# US 2006/0235895 A1 · Efficient point-to-multipoint data reconciliation

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2006/0235895 A1
- Document ID: US20060235895A1
- Status: Published application
- Kind: A1
- Application number: 11/109,011
- Filed: 2005-04-18
- Published: 2006-10-19
- Earliest claimed: 2005-04-18
- Assignees: Microsoft Corporation
- Inventors: Pablo Rodriguez; Julian Chesterfield
- Web page: https://patentgrep.com/patent/US20060235895A1

## CPC

- H04L 63/123: {received data contents, e.g. message integrity}
- H04N 21/631: {Multimode Transmission, e.g. transmitting basic layers and enhancement layers of the content over different transmission paths or transmitting with different error corrections, different keys or with different transmission protocols}
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)
- H04N: PICTORIAL COMMUNICATION, e.g. TELEVISION

## 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.

## Claims

### Claim 1

A computer-implemented method of generating update information, the method comprising:
obtaining or accessing a hash hierarchy, the hash hierarchy comprising first hashes of divisions of a dataset and second hashes of sub-divisions of the divisions of the dataset; and
automatically generating erasure hashes of the second hashes, the erasure hashes comprising different combinations of the second hashes.

### Claim 2 (depends on 1)

A computer-implemented method according to claim 1, wherein the different combinations of second hashes comprise independent linear combinations of the second hashes.

### Claim 3 (depends on 2)

A computer-implemented method according to claim 2, wherein the independent linear combinations comprise random linearly independent combinations of the second hashes.

### Claim 4 (depends on 1)

A computer-implemented method according to claim 1, wherein the erasure hashes are generated with the property that: given an erasure hash, given a first block, hash, and given combination information indicating how the second block hashes were combined to form the erasure hash, all second block hashes of a sub-division of the given first block hash's division can be calculated using the combination information, the erasure hash, and the first block hash.

### Claim 5 (depends on 4)

A computer-implemented method according to claim 4, wherein the combination information comprises a set of coefficients used to linearly combine the second block hashes.

### Claim 6 (depends on 1)

A computer-implemented method according to claim 1, wherein the first hashes, the second hashes, and the erasure hashes are computed such that, given a second block hash reconstructed using one or more erasure hashes, and given a parent first block hash which is a hash of a division containing the sub-division hashed by the reconstructed second block hash, a sibling second block hash can be computed from the parent first block hash and the reconstructed second block hash, where the sibling second block hash is a hash of another sub-division contained by the parent first block hash's division.

### Claim 7 (depends on 1)

A computer-implemented method according to claim 1, wherein each erasure hash is computed such that, given any erasure hash and a set of coefficients with which the second block hashes were combined to produce the erasure hash, there is a substantial certainty that any unknown second block hash can be derived from the erasure hash, the coefficients, and known second block hashes.

### Claim 8 (depends on 1)

A computer-implemented method according to claim 1, wherein hashes of the divisions are provided to a first communication channel, encodings of the hashes of the sub-divisions are provided to a second communication channel, and blocks of the dataset are provided to a third communication channel.

### Claim 9

A volatile or non-volatile computer-readable storage storing update information comprising encodings of hashes of a master dataset, where the encodings are to be received by receivers, where each receiver has a target dataset, where each target dataset respectively has a different unidentified portion with an equivalent in the master dataset, where each target dataset is respectively missing an unidentified different portion of the master dataset, and where the encodings are configured such that each receiver can use same encodings to identify its portion of its target dataset that has an equivalent in the master dataset.

### Claim 10 (depends on 9)

A volatile or non-volatile computer-readable storage according to claim 9, wherein the encodings comprise erasure hashes that comprise substantially unique linear combinations of the hashes of the master dataset.

### Claim 11 (depends on 10)

A volatile or non-volatile computer-readable storage according to claim 10, wherein the hashes comprises hashes of blocks of the master dataset and hashes of sub-blocks of the blocks.

### Claim 12 (depends on 10)

A volatile or non-volatile computer-readable storage according to claim 10, wherein the erasure hashes are decomposable.

### Claim 13 (depends on 9)

A volatile or non-volatile computer-readable storage according to claim 9, wherein the encodings are configured so that the encodings, known hashes, and known portions of the master dataset can be used to determine unknown hashes of the master dataset.

### Claim 14 (depends on 9)

A volatile or non-volatile computer-readable storage according to claim 9 wherein the encodings are configured so that an amount of encodings needed by a receiver to compute unknown hashes of the master dataset is proportional to an amount of known hashes of the master dataset that do not match the receiver's target dataset.

### Claim 15

A volatile or non-volatile computer-readable storage storing information for enabling a receiving device to perform a process, the process performed by the receiving device comprising:
obtaining upper hashes comprising hashes of divisions of a master dataset, the upper hashes having been generated with a hash function;
determining divisions in a target dataset that are mapped to upper hashes by the hash function;
calculating lower hashes comprising hashes of subdivisions in the target dataset whose parent divisions in the target dataset mapped to upper hashes;
receiving encodings comprising different combinations of hashes of subdivisions of the divisions of the master dataset; and
using the lower hashes and the received encodings to determine hashes of subdivisions of those of the divisions in the master dataset whose corresponding upper hashes were not mapped-to by divisions in the target dataset.

### Claim 16 (depends on 15)

A volatile or non-volatile computer-readable storage according to claim 15, wherein the determining of the hashes of the subdivisions of the divisions in the master dataset also uses information indicating how the hashes of the subdivisions of the master dataset were combined to generate the encodings.

### Claim 17 (depends on 15)

A volatile or non-volatile computer-readable storage according to claim 15, further comprising constructing a copy of the master dataset using the divisions in the target dataset that mapped to upper hashes and using reconstructed portions of the master dataset corresponding to the determined hashes of the subdivisions of the divisions in the master dataset.

### Claim 18 (depends on 17)

A volatile or non-volatile computer-readable storage according to claim 17, further comprising receiving encodings of blocks of the master dataset and using them to reconstruct the reconstructed divisions of the master dataset.

### Claim 19 (depends on 15)

A volatile or non-volatile computer-readable storage according to claim 15, wherein the upper hashes are obtained from a first communication channel, and the encodings of hashes are obtained from a second communication channel.

### Claim 20 (depends on 15)

A volatile or non-volatile computer-readable storage according to claim 15, wherein the encodings comprise erasure hashes.
