  LT codes and digital fountain techniques have received significant attention
from both academics and industry in the past few years. There have also been
extensive interests in applying LT code techniques to distributed storage
systems such as cloud data storage in recent years. However, Plank and
Thomason's experimental results show that LDPC code performs well only
asymptotically when the number of data fragments increases and it has the worst
performance for small number of data fragments (e.g., less than 100). In their
INFOCOM 2012 paper, Cao, Yu, Yang, Lou, and Hou proposed to use exhaustive
search approach to find a deterministic LT code that could be used to decode
the original data content correctly in distributed storage systems. However, by
Plank and Thomason's experimental results, it is not clear whether the
exhaustive search approach will work efficiently or even correctly. This paper
carries out the theoretical analysis on the feasibility and performance issues
for applying LT codes to distributed storage systems. By employing the
underlying ideas of efficient Belief Propagation (BP) decoding process in LT
codes, this paper introduces two classes of codes called flat BP-XOR codes and
array BP-XOR codes (which can be considered as a deterministic version of LT
codes). We will show the equivalence between the edge-colored graph model and
degree-one-and-two encoding symbols based array BP-XOR codes. Using this
equivalence result, we are able to design general array BP-XOR codes using
graph based results. Similarly, based on this equivalence result, we are able
to get new results for edge-colored graph models using results from array
BP-XOR codes.
