Patent ID: 7984018

Claim:
A method of generating update information for a dataset, the method comprising: generating, by a processor, a hash hierarchy based on the dataset, wherein the hash hierarchy includes a plurality of levels, and wherein a top level of the hash hierarchy comprises first hashes of first level subdivisions of the dataset, and wherein each subsequent level of the hash hierarchy comprises hashes of subdivisions of next higher level subdivisions of the dataset; generating, by the processor, erasure hashes based on one of the plurality of levels of the hash hierarchy, wherein each erasure hash is produced by crossing a vector of coefficients with a matrix of a portion of the hashes of the one of the plurality of levels of the hash hierarchy; and repeatedly broadcasting the erasure hashes to a receiver that is configured to compute a subset of the portion of the hashes that is unknown to the receiver based on the received erasure hash and its corresponding coefficients and another subset of the portion of the hashes that is known to the receiver.