New Storage Codes Between the MSR and MBR Points Through Block Designs

Abstract

In distributed storage systems, data are stored across multiple storage nodes which are unreliable and prone to failure. While erasure coding is more efficient than simple replication in terms of storage overhead and reliability, classic erasure codes like Reed-Solomon codes require a large repair bandwidth when repairing a failed node. Therefore, reducing both the storage overhead and repair bandwidth under a given fault tolerance is desired, however, it is not possible to minimize both. In 2007, Dimarkis et al. characterized the storage-bandwidth trade-off under functional repair. While exact repair is preferred in practical systems, it was shown that only two extremal points and a line segment are achievable under exact repair. Up to now, the storage-bandwidth trade-off under exact repair remains unresolved for general parameters. Nevertheless, constructing codes with exact repair between the two extremal points is still of great interest, however, very few such constructions have been reported in the literature. In this paper, we present explicit code constructions based on block designs, which can be viewed as a generalization of a previous work by Tian et al. Such a generalization leads to two new codes, i.e., an $(n, k=n-1, d=n-1)$ storage code based on regular mandatory representation designs (MRDs) and an $(n, k=n-2, d\ge n-2)$ storage code based on 3-designs. It is shown that the new storage codes have a better performance than the ones by Tian et al. in terms of the sub-packetization level and storage-bandwidth trade-off. In addition, the new $(n, k=n-2, d)$ storage code supports two repair degrees, i.e., $d\in \{n-2,n-1\}$ .

Keywords

• Block designs
• distributed storage
• interior points
• minimum bandwidth regenerating codes
• minimum storage regenerating codes