Ida: Frag, fragment, consistent, reconstruct - information dispersal algorithm .EX include "ida.m"; ida := load Ida Ida->PATH; Frag: adt { dlen: int; # length of original data m: int; # minimum pieces for reconstruction a: array of int; # encoding array row for this fragment enc: array of int; # encoded data tag: array of byte; # user data, such as SHA1 hash pack: fn(f: self ref Frag): array of byte; unpack: fn(d: array of byte): ref Frag; }; init: fn(); fragment: fn(data: array of byte, m: int): ref Frag; consistent: fn(frags: array of ref Frag): array of ref Frag; reconstruct: fn(frags: array of ref Frag): (array of byte, string); Ida implements Rabin's Information Dispersal Algorithm (IDA), an effective scheme for fault-tolerant storage and message routing. The algorithm breaks an array of bytes (for instance a file or a block of data) into n pieces, in such a way that the original data can be recovered using only m of them, where n and m are parameters. The module provides the fundamental operations.

Init must be called before invoking any other operation of the module.

Fragment takes an array of data , and m , the minimum number of pieces required for reconstruction, and returns a reference to a Frag value representing one encoded fragment of the data. At least m calls must be made to fragment to obtain enough such fragments to be able to rebuild the data; invariably more fragments are generated to provide the desired level of redundancy.

Each fragment Frag has the following components:

dlen The length in bytes of the data .

m The minimum number of fragments for reconstruction.

a The row of an m×m encoding matrix that corresponds to this fragment.

enc The encoded data, represented by an array of integer values. For L bytes of input data, the array will have length .\\"$ left ceil L over 2m right ceil $. .nr 12 0\w'\s+0\*(12' .nr 13 0\w'\s+0\*(13' .nr 14 \n(12 .nr 14 \n(14+0.5m \h'-\n(13u-\n(12u/2u'\v'-0.6m'\*(12\v'0.6m'\ \h'-\n(14u-\n(12u/2u+0.1m'\v'-0.3m'\l'\n(14u-0.2m'\h'0.1m'\v'0.3m' .as 11 \*(12 .lf 4 .as 11 ". \*(11 .lf 5

All those values must be stored or transmitted for later use, to reconstruct the data. The values in a are in the interval "[ 1, 65536 ]" and those in enc are in the interval "[ 0, 65536 ]."

Reconstruct takes an array frags of distinct fragments previously produced by repeated calls to fragment( data, m ) and returns a tuple ( data, err ) . Provided at least m suitable fragments are found in frags , the data returned will be that originally provided to fragment . If the parameters of the various fragments in frags disagree, or some other error occurs, data will be nil and err will contain a diagnostic. Reconstruct assumes the fragments it receives are consistent: they represent the same encoding parameters, including the value of m . If it detects an inconsistency, it returns a diagnostic.

Consistent checks the consistency of a set of fragments, and returns a new subset containing only those fragments that agree with the majority in frags on each parameter.

/appl/lib/ida/ida.b

/appl/lib/ida/idatab.b

M Rabin, ``Efficient Dispersal of Information for Security, Load Balancing, and Fault Tolerance'', JACM 36(2) , April 1989, pp. 335-348.