Hierarchical codes : a flexible trade-off for erasure codes

Duminuco, Alessandro; Biersack, Ernst W
Journal of Peer-to-Peer Networks and Applications, Vol 2, March 2009.

Redundancy is the basic technique to provide reliability in storage systems consisting of multiple components. A redundancy scheme defines how the redundant data are produced and maintained. The simplest redundancy scheme is replication, which however suffers from storage inefficiency. Another approach is erasure coding, which provides the same level of reliability as replication using a significantly smaller amount of storage. When redundant data are lost, they need to be replaced. While replacing replicated data consists in a simple copy, it becomes a complex operation with erasure codes: new data are produced performing a coding over some other available data. The amount of data to be read and coded is d times larger than the amount of data produced, where d, called repair degree, is larger than 1 and depends on the structure of the code. This implies that coding has a larger computational and I/O cost, which, for distributed storage systems, translates into increased network traffic. Participants of Peer-to-Peer systems often have ample storage and CPU power, but their network bandwidth may be limited. For these reasons existing coding techniques are not suitable for P2P storage. This work explores the design space between replication and the existing erasure codes. We propose and evaluate a new class of erasure codes, called Hierarchical Codes, which allows to reduce the network traffic due to maintenance without losing the benefits given by traditional erasure codes.

Sécurité numérique
Eurecom Ref:
© Springer. Personal use of this material is permitted. The definitive version of this paper was published in Journal of Peer-to-Peer Networks and Applications, Vol 2, March 2009.
and is available at : http://dx.doi.org/10.1007/s12083-009-0044-8

PERMALINK : https://www.eurecom.fr/publication/2848