2017/10/16 by Hyegyeong Park, Dongwon Lee, Park, Hyegyeong +3 · 1 citation
Computer Science · #Advanced Data Storage Technologies #Caching and Content Delivery #Distributed #Error Correcting Code Techniques #FOS: Computer and information sciences #Information Theory (cs.IT) #Parallel #Performance (cs.PF) #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.1710.05615
openalex publication_date 2017/10/16 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28
Distributed storage systems suffer from significant repair traffic generated\ndue to frequent storage node failures. This paper shows that properly designed\nlow-density parity-check (LDPC) codes can substantially reduce the amount of\nrequired block downloads for repair thanks to the sparse nature of their factor\ngraph representation. In particular, with a careful construction of the factor\ngraph, both low repair-bandwidth and high reliability can be achieved for a\ngiven code rate. First, a formula for the average repair bandwidth of LDPC\ncodes is developed. This formula is then used to establish that the minimum\nrepair bandwidth can be achieved by forcing a regular check node degree in the\nfactor graph. Moreover, it is shown that given a fixed code rate, the variable\nnode degree should also be regular to yield minimum repair bandwidth, under\nsome reasonable minimum variable node degree constraint. It is also shown that\nfor a given repair-bandwidth requirement, LDPC codes can yield substantially\nhigher reliability than currently utilized Reed-Solomon (RS) codes. Our\nreliability analysis is based on a formulation of the general equation for the\nmean-time-to-data-loss (MTTDL) associated with LDPC codes. The formulation\nreveals that the stopping number is closely related to the MTTDL. It is further\nshown that LDPC codes can be designed such that a small loss of\nrepair-bandwidth optimality may be traded for a large improvement in\nerasure-correction capability and thus the MTTDL.\n