logo

SCIENCE CHINA Information Sciences, Volume 61, Issue 10: 100304(2018) https://doi.org/10.1007/s11432-018-9516-6

Code constructions for multi-node exact repair in distributed storage$^\dag$

More info
  • ReceivedMar 10, 2018
  • AcceptedJul 9, 2018
  • PublishedAug 17, 2018

Abstract

We study the problem of centralized exact repair of multiple failures in distributed storage. We present constructions that achieve a new set of interior points under exact repair. The constructions build upon the layered code Construction by Tian et al., designed for exact repair of single failure. We firstly improve upon the layered Construction for general system parameters. Then, we extend the improved Construction to support the repair of multiple failures, with varying number of helpers. In particular, for some parameters,we prove the optimality of one point in terms of the storage size and the repair bandwidth for multiple erasures. Finally, considering minimum bandwidth cooperative repair (MBCR) codes as centralized repair codes, we determine explicitly the best achievable region obtained by space-sharing among all known points, including the MBCR point.


References

[1] Dimakis A G, Godfrey P, Yunnan W, et al. Network coding for distributed storage systems. IEEE Trans Inform Theor, 2010, 9: 4539--4551. Google Scholar

[2] Rashmi K V, Shah N B, Kumar P V. Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction. IEEE Trans Inform Theor, 2011, 57: 5227-5239 CrossRef Google Scholar

[3] Shah N B, Rashmi K V, Kumar P V. Interference Alignment in Regenerating Codes for Distributed Storage: Necessity and Code Constructions. IEEE Trans Inform Theor, 2012, 58: 2134-2158 CrossRef Google Scholar

[4] Suh C, Ramchandran K. Exact-Repair MDS Code Construction Using Interference Alignment. IEEE Trans Inform Theor, 2011, 57: 1425-1442 CrossRef Google Scholar

[5] Rawat A S, Koyluoglu O O, Vishwanath S. Progress on high-rate MSR codes: enabling arbitrary number of helper nodes. In: Proceedings of Information Theory and Applications Workshop, San Diego, 2016. 1--6. Google Scholar

[6] Goparaju S, Fazeli A, Vardy A. Minimum Storage Regenerating Codes for All Parameters. IEEE Trans Inform Theor, 2017, 63: 6318-6328 CrossRef Google Scholar

[7] Cadambe V R, Jafar S A, Maleki H. Asymptotic Interference Alignment for Optimal Repair of MDS Codes in Distributed Storage. IEEE Trans Inform Theor, 2013, 59: 2974-2987 CrossRef Google Scholar

[8] Tamo I, Wang Z, Bruck J. Zigzag Codes: MDS Array Codes With Optimal Rebuilding. IEEE Trans Inform Theor, 2013, 59: 1597-1616 CrossRef Google Scholar

[9] Ye M, Barg A. Explicit Constructions of High-Rate MDS Array Codes With Optimal Repair Bandwidth. IEEE Trans Inform Theor, 2017, 63: 2001-2014 CrossRef Google Scholar

[10] Vajha M, Babu B S, Kumar P V. Explicit MSR codes with optimal access, optimal sub-packetization and small field size for $~d=~k+~1,~k+~2,~k+~3$. 2018,. arXiv Google Scholar

[11] Shah N B, Rashmi K V, Kumar P V. Distributed Storage Codes With Repair-by-Transfer and Nonachievability of Interior Points on the Storage-Bandwidth Tradeoff. IEEE Trans Inform Theor, 2012, 58: 1837-1852 CrossRef Google Scholar

[12] Elyasi M, Mohajer S. Determinant Coding: A Novel Framework for Exact-Repair Regenerating Codes. IEEE Trans Inform Theor, 2016, 62: 6683-6697 CrossRef Google Scholar

[13] Elyasi M, Mohajer S. A probabilistic approach towards exact-repair regeneration codes. In: Proceedings of Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2015. 865--872. Google Scholar

[14] Tian C. A note on the rate region of exact-repair regenerating codes. 2015,. arXiv Google Scholar

[15] Tian C. Characterizing the Rate Region of the (4,3,3) Exact-Repair Regenerating Codes. IEEE J Sel Areas Commun, 2014, 32: 967-975 CrossRef Google Scholar

[16] Senthoor K, Sasidharan B, Kumar P V. Improved layered regenerating codes characterizing the exact-repair storage-repair bandwidth tradeoff for certain parameter sets. In: Proceedings of IEEE Information Theory Workshop, Jerusalem, 2015. 1--5. Google Scholar

[17] Tian C, Sasidharan B, Aggarwal V. Layered Exact-Repair Regenerating Codes via Embedded Error Correction and Block Designs. IEEE Trans Inform Theor, 2015, 61: 1933-1947 CrossRef Google Scholar

[18] Sasidharan B, Senthoor K, Kumar P V. An improved outer bound on the storage-repair-bandwidth tradeoff of exact-repair regenerating codes. In: Proceedings of IEEE International Symposium on Information Theory, Honolulu, 2014. 2430--2434. Google Scholar

[19] Duursma I M. Outer bounds for exact repair codes. 2014,. arXiv Google Scholar

[20] Sasidharan B, Prakash N, Krishnan M N. Outer bounds on the storage-repair bandwidth trade-off of exact-repair regenerating codes. IJICOT, 2016, 3: 255-298 CrossRef Google Scholar

[21] Duursma I M. Shortened regenerating codes. 2015,. arXiv Google Scholar

[22] Kermarrec A M, Le Scouarnec N, Straub G. Repairing multiple failures with coordinated and adaptive regenerating codes. In: Proceedings of International Symposium on Network Coding, Beijing, 2011. 1--6. Google Scholar

[23] Rawat A S, Koyluoglu O O, Vishwanath S. Centralized repair of multiple node failures with applications to communication efficient secret sharing. 2016,. arXiv Google Scholar

[24] Shum K W, Hu Y. Cooperative Regenerating Codes. IEEE Trans Inform Theor, 2013, 59: 7229-7258 CrossRef Google Scholar

[25] Zorgui M, Wang Z. Centralized multi-node repair in distributed storage. In: Proceedings of Annual Allerton Conference on Communication, Control, and Computing, Monticello, 2016. 617--624. Google Scholar

[26] Ye M, Barg A. Optimal MDS codes for cooperative repair. 2018,. arXiv Google Scholar

[27] Li J, Li B. Cooperative repair with minimum-storage regenerating codes for distributed storage. In: Prcoceedings of IEEE INFOCOM, Toronto, 2014. 316--324. Google Scholar

[28] Wang A, Zhang Z. Exact cooperative regenerating codes with minimum-repair-bandwidth for distributed storage. In: Prcoceedings of IEEE INFOCOM, Turin, 2013. 400--404. Google Scholar

[29] Zorgui M, Wang Z. Centralized multi-node repair for minimum storage regenerating codes. In: Proceedings of IEEE International Symposium on Information Theory, Aachen, 2017. 2213--2217. Google Scholar

[30] Goparaju S, El Rouayheb S, Calderbank R. New codes and inner bounds for exact repair in distributed storage systems. In: Proceedings of IEEE International Symposium on Information Theory, Honolulu, 2014. 1036--1040. Google Scholar

[31] Zorgui M, Wang Z. Centralized multi-node repair regenerating codes. 2017,. arXiv Google Scholar

[32] Wang Z, Tamo I, Bruck J. Optimal Rebuilding of Multiple Erasures in MDS Codes. IEEE Trans Inform Theor, 2017, 63: 1084-1101 CrossRef Google Scholar

[33] Blaum M, Brady J, Bruck J. EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures. IEEE Trans Comput, 1995, 44: 192-202 CrossRef Google Scholar

[34] Keevash P. The existence of designs. 2014,. arXiv Google Scholar

[35] Colbourn C J. CRC Handbook of Combinatorial Designs. Boca Raton: CRC Press, 2010. Google Scholar

[36] Kamath G M, Prakash N, Lalitha V. Codes With Local Regeneration and Erasure Correction. IEEE Trans Inform Theor, 2014, 60: 4637-4660 CrossRef Google Scholar

[37] Rawat A S, Silberstein N, Koyluoglu O O, et al. Optimal locally repairable codes with local minimum storage regeneration via rank-metric codes. In: Prcoceedings of Information Theory and Applications Workshop, San Diego, 2013. 1--8. Google Scholar

  • Figure 1

    A repair situation associated to given parameters $s$ and $p$.

  • Figure 2

    (Color online) Using the MSMR repair property improves upon the layered code repair performance. The exact-repair tradeoff is achieved in [12], with lower bound derived in [21].

  • Figure 3

    (Color online) Comparing achievable schemes for different scenarios. The dashed curves correspond to points achieved with Construction 1, and the solid curves (with open circles) corresponds to Construction 2, coupled with MSMR repair. The lowest solid curve corresponds to the functional repair tradeoff (1). The dotted line corresponds to space-sharing between MSMR and MBCR points. $(n,k,d,e)$ = (8,6,6,2) in (a); (9,6,7,2) in (b); (10,6,8,2) in (c); (19,16,17,2) in (d); (16,14,14,2) in (e); (24,14,14,2) in (f).

  • Figure 4

    (Color online) Functional tradeoff and optimal points achieved by Proposition 3.2.

  • Figure 5

    (Color online) Achievable points by Construction 1 for a $(n,k,d,e)=(17,14,14,3)$ system. The $x$-axis is the normalized storage per node $\bar{\alpha}$ and the $y$-axis is the normalized bandwidth $\bar{\beta}$.

  • Table 1   EVENODD code: an example of an MSRcode$^{\rm~a)b)}$
    Symbol $1$ Symbol $2$ Symbol $3$ Symbol $4$
    $a$ $c$ $a+c$ $~a+d$
    $b$ $d$ $b+d$ $b+c+d$
  • Table 2   Summary of cases for which $(\bar{\alpha}_r,\bar{\beta}_r)$ is a corner point in $\mathcal{R}$ $^{\rm~a)}$
    $(\bar{\alpha}_r,~\bar{\beta}_r)$ $k~<~k_{\rm~th}(p)$ $k~\geq~k_{\rm~th}(p)$
    $~p~\le~p_{\max}$ $\checkmark$ $\text{\ding{55}}$
    $p~>~p_{\max}$ $\checkmark$ $\checkmark$

Copyright 2020 Science China Press Co., Ltd. 《中国科学》杂志社有限责任公司 版权所有

京ICP备18024590号-1       京公网安备11010102003388号