Fractal codes with locality and availability

Peter Farkaš; Katarína Farkašová; Frederik Pavelka

doi:10.2478/jee-2025-0036

Abstract

Codes with locality and availability are used in distributed storage for data recovery. Locality λ enables the recovery of lost data on each server by exploiting data from only λ remaining intact servers. Availability α means that an α subset of servers providing localities are available for data recovery for each server. The secondary benefit of these codes in distributed storage is that they allow access to hot data in times of high demand, exploiting locality and availability. In this paper two families of codes with locality availability and scalability are presented which can be represented as fractals.

References

W. Jiang, H. Jiang, J. Wu and Q. Chen, “Accelerating Distributed Cloud Storage Systems with In-Network Computing,” in IEEE Network, vol. 37, no. 4, pp. 64-70, July/August 2023, doi: 10.1109/MNET.002.2200631.
Search in Google Scholar Back to article
S. Rafati Niya; B. Stiller, “Enabling Technologies and Distributed Storage,” in Blockchains: Empowering Technologies and Industrial Applications, IEEE, 2024, pp. 21-51, doi: 10.1002/9781119781042.ch2.
Search in Google Scholar Back to article
A. G. Dimakis, K. Ramchandran, Y. Wu and C. Suh, “A Survey on Network Codes for Distributed Storage,” in Proceedings of the IEEE, vol. 99, no. 3, pp. 476-489, March 2011, doi: 10.1109/JPROC.2010.2096170.
Search in Google Scholar Back to article
M. Blaum, J. Brady, J. Bruck and Jai Menon, “EVENODD: an efficient scheme for tolerating double disk failures in RAID architectures,” in IEEE Transactions on Computers, vol. 44, no. 2, pp. 192-202, Feb. 1995, doi: 10.1109/12.364531.
Search in Google Scholar Back to article
B. H. Marcus, R. M. Roth, and P. H. Siegel, “Constrained systems and coding for recording channels,” in Handbook of Coding Theory, V. Pless and W. C. Huffman, Eds., 1998, pp. 1635–1764
Search in Google Scholar Back to article
P. Gopalan, C. Huang, H. Simitci and S. Yekhanin, “On the Locality of Codeword Symbols,” in IEEE Transactions on Information Theory, vol. 58, no. 11, pp. 6925-6934, Nov. 2012, doi: 10.1109/TIT.2012.2208937.
Search in Google Scholar Back to article
M. Shahabinejad, M. Khabbazian and M. Ardakani, “A Class of Binary Locally Repairable Codes,” in IEEE Transactions on Communications, vol. 64, no. 8, pp. 3182-3193, Aug. 2016, doi: 10.1109/TCOMM.2016.2581163.
Search in Google Scholar Back to article
B. Zhu and H. Li, “Exploring Node Repair Locality in Fractional Repetition Codes,” in IEEE Communications Letters, vol. 20, no. 12, pp. 2350-2353, Dec. 2016, doi: 10.1109/LCOMM.2016.2605100.
Search in Google Scholar Back to article
X. Zhang, “Modified Generalized Integrated Interleaved Codes for Local Erasure Recovery,” in IEEE Communications Letters, vol. 21, no. 6, pp. 1241-1244, June 2017, doi: 10.1109/LCOMM.2017.2675905.
Search in Google Scholar Back to article
X. Zhang, S. Sprouse and I. Ilani, “A Flexible and Low-Complexity Local Erasure Recovery Scheme,” in IEEE Communications Letters, vol. 20, no. 11, pp. 2129-2132, Nov. 2016, doi: 10.1109/LCOMM.2016.2604307.
Search in Google Scholar Back to article
M.-Y. Nam and H. -Y. Song, “Binary Locally Repairable Codes with Minimum Distance at Least Six Based on Partial t -Spreads,” in IEEE Communications Letters, vol. 21, no. 8, pp. 1683-1686, Aug. 2017, doi: 10.1109/LCOMM.2017.2697424.
Search in Google Scholar Back to article
M. Shahabinejad, M. Khabbazian and M. Ardakani, “On the Average Locality of Locally Repairable Codes,” in IEEE Transactions on Communications, vol. 66, no. 7, pp. 2773-2783, July 2018, doi: 10.1109/TCOMM.2017.2712186.
Search in Google Scholar Back to article
X. Zhang and Z. Xie, “Relaxing the Constraints on Locally Recoverable Erasure Codes by Finite Field Element Variation,” in IEEE Communications Letters, vol. 23, no. 10, pp. 1680-1683, Oct. 2019, doi: 10.1109/LCOMM.2019.2927668.
Search in Google Scholar Back to article
C. Rajput and M. Bhaintwal, “Cyclic LRC-LCD Codes with Hierarchical Locality,” in IEEE Communications Letters, vol. 25, no. 3, pp. 711-715, March 2021, doi: 10.1109/LCOMM.2020.3040170.
Search in Google Scholar Back to article
Q. Fu, R. Li and S. Yang, “Optimal (r, δ)-Locally Repairable Codes from Simplex Code and Cap Code,” in IEEE Access, vol. 8, pp. 215414-215418, 2020, doi: 10.1109/ACCESS.2020.3040320.
Search in Google Scholar Back to article
B. Andrade, C. Carvalho, V. G. L. Neumann and A. C. P. Veiga, “A Family of Codes with Locality Containing Optimal Codes,” in IEEE Access, vol. 10, pp. 39145-39153, 2022, doi: 10.1109/ACCESS.2022.3165032.
Search in Google Scholar Back to article
X. Lin, “A Note on Bandwidth-Optimal Repair Scheme for Reed-Solomon Codes with Low Repair Locality,” in IEEE Communications Letters, vol. 27, no. 11, pp. 2924-2927, Nov. 2023, doi: 10.1109/LCOMM.2023.3319653.
Search in Google Scholar Back to article
J. Wang, K. Shen, X. Liu and C. Yu, “Construction of Binary Locally Repairable Codes with Optimal Distance and Code Rate,” in IEEE Communications Letters, vol. 25, no. 7, pp. 2109-2113, July 2021, doi: 10.1109/LCOMM.2021.3075520.
Search in Google Scholar Back to article
A. Singh Rawat, D. S. Papailiopoulos and A. G. Dimakis, “Availability and locality in distributed storage,” 2013 IEEE Global Conference on Signal and Information Processing, Austin, TX, USA, 2013, pp. 923-928, doi: 10.1109/GlobalSIP.2013.6737043.
Search in Google Scholar Back to article
J. Hao and S.-T. Xia, “Constructions of Optimal Binary Locally Repairable Codes with Multiple Repair Groups,” in IEEE Communications Letters, vol. 20, no. 6, pp. 1060-1063, June 2016, doi: 10.1109/LCOMM.2016.2539160.
Search in Google Scholar Back to article
J.-H. Kim and H.-Y. Song, “Alphabet-Dependent Bounds for Locally Repairable Codes with Joint Information Availability,” in IEEE Communications Letters, vol. 21, no. 8, pp. 1687-1690, Aug. 2017, doi: 10.1109/LCOMM.2017.2699968.
Search in Google Scholar Back to article
N. Silberstein, A. Zeh, “Anticode-based locally repairable codes with high availability,” Designs, Codes and Cryptography, pp. 419-445, 2018, doi: 86. 10.1007/s10623-017-0358-0.
Search in Google Scholar Back to article
C. Kim and J.-S. No, “New Constructions of Binary LRCs with Disjoint Repair Groups and Locality 3 Using Existing LRCs,” in IEEE Communications Letters, vol. 23, no. 3, pp. 406-409, March 2019, doi: 10.1109/LCOMM.2019.2892950.
Search in Google Scholar Back to article
U. D. Kadiyam and S. Das, “A Class of Codes with Availability and Multiple Local-Erasures Correction,” in IEEE Communications Letters, vol. 24, no. 10, pp. 2087-2091, Oct. 2020, doi: 10.1109/LCOMM.2020.3004757.
Search in Google Scholar Back to article
G. Zhang, “A New Construction of Optimal (r, δ) Locally Recoverable Codes,” in IEEE Communications Letters, vol. 24, no. 9, pp. 1852-1856, Sept. 2020, doi: 10.1109/LCOMM.2020.2998587.
Search in Google Scholar Back to article
U. D. Kadiyam and S. Das, “Codes with Availability for Multiple Code Symbols,” in IEEE Communications Letters, vol. 25, no. 8, pp. 2477-2481, Aug. 2021, doi: 10.1109/LCOMM.2021.3079358.
Search in Google Scholar Back to article
U. D. Kadiyam and S. Das, “Codes with Availability for Multiple Code Symbols,” in IEEE Communications Letters, vol. 25, no. 8, pp. 2477-2481, Aug. 2021, doi: 10.1109/LCOMM.2021.3079358.
Search in Google Scholar Back to article
E. Wang, J. Wang, L. Jinghui, Y. Jiarong, Construction of optimal locally repairable codes based on Latin squares, Journal of Beijing University of Posts and Telecommunications, vol. 46, no. 5, pp. 8-14, Oct. 2023, doi: 10.13190/j.jbupt.2022-214
Search in Google Scholar Back to article
P. Farkaš, “Scalable Family of Codes with Locality and Availability for Information Repair in Distributed Storage Systems,” 2019 4th International Conference on Smart and Sustainable Technologies (SpliTech), Split, Croatia, 2019, pp. 1-4, doi: 10.23919/SpliTech.2019.8783148.
Search in Google Scholar Back to article
V. I. Shynkarenko, “Constructive-synthesizing representation of geometric fractals,” Cybernetics and Systems Analysis, Vol. 55, No. 2, March, 2019, pp. 186-199, doi: 10.1007/s10559-019-00123-w
Search in Google Scholar Back to article
V. Shynkarenko, O. Letuchyi and R. Chyhir, “Constructive-synthesizing modeling of fractal crystal lattices,” 2023 IEEE 18th International Conference on Computer Science and Information Technologies (CSIT), Lviv, Ukraine, 2023, pp. 1-4, doi: 10.1109/CSIT61576.2023.10324251.
Search in Google Scholar Back to article
P. Farkaš, “Linear block code with locality and availability inspired by tetrahedron,” Journal of Electrical Engineering, Vol. 75, No. 1, February 2024, pp. 72-76, doi: https://doi.org/10.2478/jee-2024-0010.
Search in Google Scholar Back to article

Fractal codes with locality and availability

Abstract

Paradigm

My account