Abstract
In this work, we propose two new types of codes with locality, namely, locally maximal recoverable (LMR) codes and \(\lambda \)-maximally recoverable (\(\lambda \)-MR) codes. The LMR codes are a subclass of codes with \((r, \delta )\)-locality such that they can correct h additional erasures in any one local set, in addition to having \((r, \delta )\)-locality. These codes are a restricted case of maximally recoverable (MR) codes, which enable recovery from all information-theoretically correctable erasure patterns in a local set. The \(\lambda \)-MR codes are a subclass of LMR codes which can also handle \(\lambda \) erasures from any coordinate positions. We give constructions for both of these families of codes. We also study the LMR codes that satisfy the complementary dual property. It is well known that codes with this property are capable of safeguarding communication systems against fault injection attacks. We give a construction of distance-optimal cyclic LMR codes that satisfy the complementary dual property.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Data availability
No data was used for the research described in the article.
References
Blaum M., Hafner J.L., Hetzler S.: Partial-MDS codes and their application to raid type of architectures. IEEE Trans. Inf. Theory 59(7), 4510–4519 (2013).
Cai H., Schwartz M.: A bound on the minimal field size of LRCs, and cyclic MR codes that attain it. IEEE Trans. Inf. Theory 69(4), 2240–2260 (2022).
Cai H., Miao Y., Schwartz M., Tang X.: A construction of maximally recoverable codes with order-optimal field size. IEEE Trans. Inf. Theory 68(1), 204–212 (2021).
Carlet C., Guilley S.: Complementary dual codes for counter-measures to side-channel attacks. In: ICMCTA, pp. 97–105 (2014). Springer.
Chen M., Huang C., Li J.: On the maximally recoverable property for multi-protection group codes. In: 2007 IEEE International Symposium on Information Theory, pp. 486–490 (2007). IEEE.
Gabrys R., Yaakobi E., Blaum M., Siegel P.H.: Constructions of partial MDS codes over small fields. IEEE Trans. Inf. Theory 65(6), 3692–3701 (2018).
Gopalan P., Huang C., Simitci H., Yekhanin S.: On the locality of codeword symbols. IEEE Trans. Inf. Theory 58(11), 6925–6934 (2012).
Gopalan P., Huang C., Jenkins B., Yekhanin S.: Explicit maximally recoverable codes with locality. IEEE Trans. Inf. Theory 60(9), 5245–5256 (2014).
Goparaju S., Calderbank R.: Binary cyclic codes that are locally repairable. In: 2014 IEEE International Symposium on Information Theory, pp. 676–680 (2014). IEEE.
Gopi S., Guruswami V.: Improved maximally recoverable LRCs using skew polynomials. IEEE Trans. Inf. Theory 68(11), 7198–7214 (2022).
Gopi S., Guruswami V., Yekhanin S.: Maximally recoverable LRCs: a field size lower bound and constructions for few heavy parities. IEEE Trans. Inf. Theory 66(10), 6066–6083 (2020).
Guruswami V., Jin L., Xing C.: Constructions of maximally recoverable local reconstruction codes via function fields. IEEE Trans. Inf. Theory 66(10), 6133–6143 (2020).
Huang C., Simitci H., Xu Y., Ogus A., Calder B., Gopalan P., Li J., Yekhanin S.: Erasure coding in windows azure storage. In: 2012 USENIX Annual Technical Conference (USENIX ATC 12), pp. 15–26 (2012).
Kamath G.M., Prakash N., Lalitha V., Kumar P.V.: Codes with local regeneration and erasure correction. IEEE Trans. Inf. Theory 60(8), 4637–4660 (2014).
Liu J., Mesnager S., Tang D.: Constructions of optimal locally recoverable codes via Dickson polynomials. Des. Codes Cryptogr. 88, 1759–1780 (2020).
Nair A.M., Lalitha V. Maximally recoverable codes with hierarchical locality. In: 2019 National Conference on Communications (NCC), pp. 1–6 (2019). IEEE.
Papailiopoulos D.S., Dimakis A.G.: Locally repairable codes. IEEE Trans. Inf. Theory 60(10), 5843–5855 (2014).
Rajput C., Bhaintwal M.: Cyclic LRC-LCD codes with hierarchical locality. IEEE Commun. Lett. 25(3), 711–715 (2020).
Rajput C., Bhaintwal M., Bandi R.: On cyclic LRC codes that are also LCD codes. In: 2020 5th International Conference on Computing, Communication and Security (ICCCS), pp. 1–5 (2020). IEEE.
Shahabinejad M., Khabbazian M., Ardakani M.: An efficient binary locally repairable code for Hadoop distributed file system. IEEE Commun. Lett. 18(8), 1287–1290 (2014).
Silberstein N., Rawat A.S., Koyluoglu O.O., Vishwanath S.: Optimal locally repairable codes via rank-metric codes. In: 2013 IEEE International Symposium on Information Theory, pp. 1819–1823 (2013). IEEE.
Sung C.W., Shum K.W., Yu Q., Xu G. Maximally recoverable codes: Connections to generic network coding and maximal matching. In: 2017 IEEE Information Theory Workshop (ITW), pp. 36–40 (2017). IEEE.
Tan P., Zhou Z., Yan H., Parampalli U.: Optimal cyclic locally repairable codes via cyclotomic polynomials. IEEE Commun. Lett. 23(2), 202–205 (2018).
Yang X., Massey J.L.: The condition for a cyclic code to have a complementary dual. Discrete Math. 126(1–3), 391–393 (1994).
Acknowledgements
This research is partially supported by Science and Engineering Research Board (SERB), India, under Grant No. CRG/2020/003785. The first author would like to thank the University Grants Commission, India, for providing financial support.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors have no Conflict of interest to declare that are relevant to the content of this article.
Additional information
Communicated by S. Li.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Rajpurohit, R.P., Bhaintwal, M. & Rajput, C. Locally maximal recoverable codes and LMR-LCD codes. Des. Codes Cryptogr. 92, 2881–2899 (2024). https://doi.org/10.1007/s10623-024-01419-5
Received:
Revised:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10623-024-01419-5