Erasure codes for distributed storage systems (DSS) are required to offer systematic encoding, low repair locality, low encoding/decoding complexity, and low decoding/storage overhead. However, the information theoretical bounds have shown that all these metrics might need to be carefully traded-off with one another. In this paper, we consider systematic Fountain codes with belief propagation (BP) decoding for massive scale DSSs. Analyzing the role of some degrees in the BP decoding process, we propose using the truncated Poisson distribution (TPD) for encoded symbol degrees. Identifying encoded symbol redundancy as a factor that degrades decoding overhead, we derive the probability of redundancy during the BP decoding process and use this as a tool for determining the Poisson parameter. Our proposed solution nicely addresses the first three DSS metrics with a slight toll on storage/decoding overhead. Through simulations, we show that the decoding overhead performance of the proposed scheme exhibits significant improvement over some existing Fountain code degree distributions in the literature. For instance, at a decoding overhead of 60%, we achieve a data loss probability closely approaching 10-4, while other Fountain codes compared are about a factor of 102higher.

This study introduces a novel framework and analysis tool to monitor the evolution of the ripple size during the Luby‐transform (LT) decoding process. It provides a closed‐form probability expression to statistically describe the behaviour of the ripple size at each step of the decoding. The probability function is conditioned on the size of the ripple in the previous step, the number of recovered source symbols and the encoded symbols' degree distribution. The authors further derive a closed‐form expression for the ripple size after new encoded symbols are received by a decoder with an empty ripple. This relates to the activation of belief propagation decoding attempts once premature terminations occur. They validate their analyses through numerical examples of an LT‐coded system. The results show that their analyses precisely coincide with the numerical results.