Fault-tolerant distributed digital storage

1. A method for operating a distributed digital storage system comprising at least one processor and a plurality of digital storage devices, the method comprising:

using the at least one processor to direct storing of a set of k source data symbols, wherein k is an integer greater than 1, on the plurality of digital storage devices by:

generating a plurality of encoding symbols from the set of k source data symbols using a Fountain encoder;

wherein generating the plurality of encoding symbols comprises systematic encoding via concatenation of the k source data symbols with a number of non-systematic symbols;

wherein each of the non-systematic symbols comprises a subset of d source data symbols selected uniformly at random from the set of k source data symbols and the Fountain encoded symbols are calculated as an exclusive-or combination of the uniformly selected subset of d source data symbols;

wherein a distribution for d=2,3, . . . k, comprises a multi-objective optimization performed in the following steps:

(i) determining probability of failure P fail of a Belief Propagation decoder;

(ii) maximizing the probability of successful decoding based on P fail ;

(iii) minimizing an average encoding/decoding complexity to obtain an objective value ƒ*.

(iv) minimizing an average repair locality subject to a constraint based on the objective value ƒ* for an expected encoding degree E(Ω(d));

storing the plurality of encoding symbols over the plurality of digital storage devices;

wherein the steps (i)-(iv) enable:

determining a minimum repair locality within the set of the k source data symbols; and

reducing computational complexity during decoding of a random subset of the encoded symbols by using a low complexity decoder.

2. The method of claim 1 , comprising a Fountain erasure encoding algorithm that uses a pre-determined distribution over an alphabet 1, . . . ,k.

3. The method of claim 2 , wherein the pre-determined distribution is such that d=1 has a probability of zero, and d=2,3, . . . k, have probabilities that are determined via a numerical optimization.

4. The method of claim 2 , wherein average repair locality is determined via a Fountain code locality probability function.

5. The method of claim 1 wherein a repair locality of a k source data symbol is defined as a least encoding degree of output neighbors of the k source data symbol.

6. The method of claim 1 , wherein the systematic encoding yields a sparsely-connected bipartite graph.

7. The method of claim 1 , where the low-complexity decoder is a Belief Propagation (BP) decoder over a binary erasure channel.

8. The method of claim 1 , wherein the Fountain encoder comprises generating encoding symbols that are BP-decodable.

9. Programmed media for use with a distributed digital storage system comprising at least one processor and a plurality of digital storage devices, comprising:

a code stored on non-transitory computer readable storage media compatible with the at least one processor, the code containing instructions to direct the at least one processor to store a set of k source data symbols, wherein k is an integer greater than 1, on the plurality of digital storage devices by:

generating a plurality of encoding symbols from the set of k source data symbols using a Fountain encoder;

wherein generating the plurality of encoding symbols comprises systematic encoding via concatenation of the k source data symbols with a number of non-systematic symbols;

wherein each of the non-systematic symbols comprises a subset of d source data symbols selected uniformly at random from the set of k source data symbols and the Fountain encoded symbols are calculated as an exclusive-or combination of the uniformly selected subset of d source data symbols;

wherein a distribution for d=2,3, . . . k, comprises a multi-objective optimization performed in the following steps:

(i) determining probability of failure P fail of a Belief Propagation decoder;

(ii) maximizing the probability of successful decoding based on P fail ;

(iii) minimizing an average encoding/decoding complexity to obtain an objective value ƒ*.

(iv) minimizing an average repair locality subject to a constraint based on the objective value ƒ* for an expected encoding degree E(Ω(d));

wherein the steps (i)-(iv) enable:

determining a minimum repair locality within the set of the k source data symbols; and

reducing computational complexity during decoding of a random subset of the encoded symbols by using a low complexity decoder.

10. The programmed media of claim 9 , comprising a Fountain erasure encoding algorithm that uses a pre-determined distribution over an alphabet 1, . . . ,k.

11. The programmed media of claim 10 , wherein the pre-determined distribution is such that d=1 has a probability of zero, and d=2,3, . . . k, have probabilities that are determined via a numerical optimization.

12. The programmed media of claim 10 , wherein average repair locality is determined via a Fountain code locality probability function.

13. The programmed media of claim 9 , wherein a repair locality of a source data symbol is defined as a least encoding degree of output neighbors of the source data symbol.

14. The programmed media of claim 9 , wherein the systematic encoding yields a sparsely-connected bipartite graph.

15. The programmed media of claim 9 , where the low-complexity decoder is a Belief Propagation (BP) decoder over a binary erasure channel.

16. The programmed media of claim 9 , wherein the Fountain encoder comprises generating encoding symbols that are BP-decodable.

17. A distributed digital storage system comprising:

at least one processor;

a plurality of digital storage devices; and

the programmed non-transitory computer readable storage media of claim 9 .