Scalar MSCR Codes via the Product Matrix Construction
- 9 August 2019
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 66 (2) , 995-1006
Abstract
An (n,k,d) cooperative regenerating code provides the optimal-bandwidth repair for any t (t>1) node failures in a cooperative way. In particular, an MSCR (minimum storage cooperative regenerating) code retains the same storage overhead as an (n,k) MDS code. Suppose each node stores α symbols which indicates the sub-packetization level of the code. A scalar MSCR code attains the minimum sub-packetization, i.e., α = d - k + t. By now, all existing constructions of scalar MSCR codes restrict to very special parameters, eg. d = k or k = 2, etc. In a recent work, Ye and Barg construct MSCR codes for all n, k, d, t, however, their construction needs α ≈ exp(nt) which is almost infeasible in practice. In this paper, we give an explicit construction of scalar MSCR codes for all d ≥ max{2k - 1 - t, k}, which covers all possible parameters except the case of k ≤ d ≤ 2k - 2 - t when k < 2k - 1 - t. Moreover, as a complementary result, for k < d < 2k - 2 - t we prove the nonexistence of linear scalar MSCR codes that have invariant repair spaces. Our construction and most of the previous scalar MSCR codes all have invariant repair spaces and this property is appealing in practice because of convenient repair. In this sense, this work presents an almost full description of usual scalar MSCR codes.Keywords
All Related Versions
Funding Information
- National Natural Science Foundation of China (61872353)
This publication has 18 references indexed in Scilit:
- Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair BandwidthIEEE Transactions on Information Theory, 2017
- Optimal Rebuilding of Multiple Erasures in MDS CodesIEEE Transactions on Information Theory, 2016
- Explicit Minimum Storage Regenerating CodesIEEE Transactions on Information Theory, 2016
- Cooperative repair of multiple node failures in distributed storage systemsInternational Journal of Information and Coding Theory, 2016
- A high-rate MSR code with polynomial sub-packetization level2015
- Cooperative repair with minimum-storage regenerating codes for distributed storage2014
- Repairing multiple failures in the Suh-Ramchandran regenerating codes2013
- Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage2013
- Cooperative Regenerating Codes for Distributed Storage Systems2011
- Network Coding for Distributed Storage SystemsIEEE Transactions on Information Theory, 2010