Exact-Repair MDS Codes for Distributed Storage Using Interference Alignment

被引:51
作者
Suh, Changho [1 ]
Ramchandran, Kannan [1 ]
机构
[1] Univ Calif Berkeley, Wireless Fdn, Berkeley, CA 94720 USA
来源
2010 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY | 2010年
关键词
D O I
10.1109/ISIT.2010.5513263
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
The high repair cost of (n, k) Maximum Distance Separable (MDS) erasure codes has recently motivated a new class of codes, called Regenerating Codes, that optimally trade off storage cost for repair bandwidth. In this paper, we address bandwidth-optimal (n, k, d) Exact-Repair MDS codes, which allow for any failed node to be repaired exactly with access to arbitrary d survivor nodes, where k <= d <= n - 1. Under scalar-linear codes which do not permit symbol-splitting, we construct Exact-Repair MDS codes that are optimal in repair bandwidth for the case of k/n <= 1/2 and d >= 2k - 1. Our codes are deterministic and require a finite-field size of at most 2(n - k). Under vector-linear codes which allow for the break-up of stored symbols into arbitrarily small subsymbols, we show the existence of optimal Exact-Repair codes for the entire admissible range of possible (n, k, d), i.e., k < n and k <= d <= n - 1. That is, we establish the existence of vector-linear Exact-Repair MDS codes that match the fundamental cutset lower bound. Our approach for both the constructive scalar-linear code design and for the existence of vector-linear codes is based on interference alignment techniques.
引用
收藏
页码:161 / 165
页数:5
相关论文
共 50 条
[21]   A New Construction of Exact-Repair MSR Codes Using Linearly Dependent Vectors [J].
Guan, Sheng ;
Kan, Haibin ;
Wen, Jie ;
Xia, Shuli .
IEEE COMMUNICATIONS LETTERS, 2017, 21 (08) :1691-1694
[22]   High-Rate Constructions of Exact-Repair Regenerating Codes [J].
Zeng, Zhiwei ;
Zhu, Bing ;
Zhao, Xuyu ;
Wang, Weiping .
2022 IEEE WIRELESS COMMUNICATIONS AND NETWORKING CONFERENCE (WCNC), 2022, :1099-1104
[23]   Determinant Coding: A Novel Framework for Exact-Repair Regenerating Codes [J].
Elyasi, Mehran ;
Mohajer, Soheil .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2016, 62 (12) :6683-6697
[24]   The Rate Region of Secure Exact-Repair Regenerating Codes for 5 Nodes [J].
Ye, Fangwei ;
Shum, Kenneth W. ;
Yeung, Raymond W. .
2016 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY, 2016, :1406-1410
[25]   Improved Layered Regenerating Codes Characterizing the Exact-Repair Storage-Repair Bandwidth Tradeoff for Certain Parameter Sets [J].
Senthoor, Kaushik ;
Sasidharan, Birenjith ;
Kumar, P. Vijay .
2015 IEEE INFORMATION THEORY WORKSHOP (ITW), 2015,
[26]   Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions [J].
Shah, Nihar B. ;
Rashmi, K. V. ;
Kumar, P. Vijay ;
Ramchandran, Kannan .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2012, 58 (04) :2134-2158
[27]   On Secure Exact-Repair Regenerating Codes With a Single Pareto Optimal Point [J].
Ye, Fangwei ;
Liu, Shiqiu ;
Shum, Kenneth W. ;
Yeung, Raymond W. .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2020, 66 (01) :176-201
[28]   Scalable (n, k, d) Exact-Repair Regenerating Codes with Small Repair Bandwidth [J].
Elyasi, Mehran ;
Mohajer, Soheil .
2017 IEEE INTERNATIONAL CONFERENCE ON COMMUNICATIONS (ICC), 2017,
[29]   A Generic Transformation to Enable Optimal Repair in MDS Codes for Distributed Storage Systems [J].
Li, Jie ;
Tang, Xiaohu ;
Tian, Chao .
IEEE TRANSACTIONS ON INFORMATION THEORY, 2018, 64 (09) :6257-6267
[30]   New Codes and Inner Bounds for Exact Repair in Distributed Storage Systems [J].
Goparaju, Sreechakra ;
El Rouayheb, Salim ;
Calderbank, Robert .
2014 48TH ANNUAL CONFERENCE ON INFORMATION SCIENCES AND SYSTEMS (CISS), 2014,