Failure-tolerant distributed storage with compressed (1 out-of N) codes

Deletion-tolerant codes provide data availability despite storage failures and are commonly used for disk arrays and reliable storage in distributed systems. The codes used for that base on binary parity or on sophisticated cyclic codes with minimal storage overhead. But the calculations for these codes cause either a noticeable number of computation cycles or require a huge number of logic gates. In this paper, a different class of deletion-tolerant codes – compressed (1 out-of N) codes – are analyzed with a focus on their application for distributed storage systems. It is shown that these codes when combined with compression can provide nearly the same low storage overhead as the traditional codes and allow a proper parallelization. Several variants of the code within the design space are discussed. A projection of the (1 out-of N) coding principle to a distributed protocol across storage units shows that the compression effort can be hidden in the communication and storage principles.