Adaptive-and-Resolvable Fractional Repetition Codes Based on Hypergraph

• Tiantian Wang,
• Jing Wang,
• Haipeng Wang,
• Jie Meng,
• Chunlei Yu,
• Shuxia Wang,

Vol. 17, No. 4, April 30, 2023
10.3837/tiis.2023.04.008, Download Paper (Free):

• Fractional Repetition (FR) codes
• distributed storage systems (DSS)
• adaptive-and-resolvable FR codes
• hypergraph
• heterogeneous distributed storage systems

Abstract

Fractional repetition (FR) codes can achieve exact uncoded repair for multiple failed nodes, with lower computational complexity and bandwidth overhead, and effectively improve repair performance in distributed storage systems (DSS). The actual distributed storage system is dynamic, that is, the parameters such as node storage overhead and number of storage nodes will change randomly and dynamically. Considering that traditional FR codes cannot be flexibly applied to dynamic distributed storage systems, a new construction scheme of adaptive-and-resolvable FR codes based on hypergraph coloring is proposed in this paper. Specifically, the linear uniform regular hypergraph can be constructed based on the heuristic algorithm of hypergraph coloring proposed in this paper. Then edges and vertices in hypergraph correspond to nodes and coded packets of FR codes respectively, further, FR codes is constructed. According to hypergraph coloring, the FR codes can achieve rapid repair for multiple failed nodes. Further, FR codes based on hypergraph coloring can be generalized to heterogeneous distributed storage systems. Compared with Reed-Solomon (RS) codes, simple regenerating codes (SRC) and locally repairable codes (LRC), adaptive-and-resolvable FR codes have significant advantages over repair locality, repair bandwidth overhead, computational complexity and time overhead during repairing failed nodes.

Statistics

Cite this article