Layered Encoding With Galois Fourier Transform For Burst Erasure Recovery In Distributed Cloud Storage Systems

Öz

Burst erasures caused by rack level failures, correlated hardware faults, and network partitions challenge the reliability of distributed cloud storage. This article presents a Galois Fourier Transform (GFT) layered encoding of data which is more resistance to these failures and prioritizes the recovery of more important data. The method uses a two layer encoding structure, dividing data into base and enhancement layer. It uses GFT to encode symbols based on the efficiency in the number of nodes. To address burst erasures, a decoder which adaptively recovers base from the preserved encoded fragments is presented. Simulations show that the proposed adaptive decoder method recovers the base layer through severe bursts of the preserved enhanced layer. Therefore, it reveals that field transforms redundancy and operates as a low overhead, priority aware coding solution for future cloud storage systems.

Anahtar Kelimeler

• Burst erasure recovery
• Galois fourier transform
• Layered erasure coding
• Priority data protection

Kaynakça

1. Alzahrani, A., Alyas, T., Alissa, K., Abbas, Q., Alsaawy, Y., & Tabassum, N. (2022). Hybrid approach for improving the performance of data reliability in cloud storage management. Sensors, 22(15), 5966. https://doi.org/10.3390/s22165966
2. Bakirov, A., Matrassulova, D., Vitulyova, Y., & Auyezov, A. (2024). The specifics of the Galois field GF(257) and its use for digital signal processing. Scientific Reports, 14(1), 15376. https://doi.org/10.1038/s41598-024-66332-2
3. Blahut, R. E. (1983). Theory and practice of error control codes. Addison-Wesley.
4. Blahut, R. E. (2003). Algebraic codes for data transmission. Cambridge University Press.
5. Edward, S., & Tony, W. (2020). Building matrices with prescribed size and number of invertible submatrices. European Journal of Combinatorics, 83, 103016. https://doi.org/10.1016/j.ejc.2019.103016
6. Farkaš, P., & Rakús, M. (2023). Run length limited error control codes derived from reed solomon codes. Wireless Personal Communications, 133(1), 795–810. https://doi.org/10.1007/s11277-023-10791-9
7. Gao, S. (2003). A new algorithm for decoding Reed-Solomon codes. In Communications, Information and Network Security (The Springer International Series in Engineering and Computer Science, Vol. 712). Springer. https://doi.org/10.1007/978-1-4757-3789-9_5
8. Gordon, G. M. (1976). Very simple method to find the minimum polynomial of an arbitrary nonzero element of a finite field. Electronics Letters, 12(24), 663–664.

9. Hostetter, M. (2020). Galois: A performant NumPy extension for Galois fields. https://github.com/mhostetter/galois
10. Hou, H., Shum, K. W., Chen, M., & Li, H. (2016). BASIC codes: low-complexity regenerating codes for distributed storage systems. IEEE Transactions on Information Theory, 62(6), 3053–3069. https://doi.org/10.1109/TIT.2016.2553670
11. Khan, A. Q., Matskin, M., Prodan, R., & Waseem, H. (2024). Cloud storage tier optimization through storage object classification. Computing, 106(12), 3389–3418. https://doi.org/10.1007/s00607-024-01281-2
12. Maxime, G., Dante, D., Sanchez, G., Haochen, P., Bogdan, N., Sicheng, Z., Hai, D., Valerie, H., Greg, P., Jesus, C., Kyle, C., & Ian, F. (2025). D-Rex: Heterogeneity-aware reliability framework and adaptive algorithms for distributed storage. In Proceedings of the 39th ACM International Conference on Supercomputing (ICS '25) (pp. 853–867). Association for Computing Machinery. https://doi.org/10.1145/3721145.3730412
13. Mingyu L, Li P, Shijun L. 2022. Effeclouds: A cost-effective cloud-of-clouds framework for two-tier storage. Future Gener Comput Syst, 129: 33-49, ISSN 0167-739X, https://doi.org/10.1016/j.future.2021.11.012
14. Ong, K. L. (2023). Burst error-correcting quantum stabilizer codes designed from idempotents. Quantum Information Processing, 22(4), 158. https://doi.org/10.1007/s11128-023-03904-7
15. Oppenheim, A. V., & Schafer, R. W. (2010). Discrete-time signal processing (3rd ed.). Pearson Print.
16. Rashimi, K., Ali, S. A., Padmanabhan, B., & Vinod, V. (2011). Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction. IEEE Transactions on Information Theory, 57(8), 5227–5239. https://doi.org/10.1109/TIT.2011.2159049
17. Reed, I. S., & Solomon, G. (1960). Polynomial codes over certain finite fields. Journal of the Society for Industrial and Applied Mathematics, 8(2), 300–304. http://dx.doi.org/10.1137/0108018
18. Shu, L., & Costello Jr., D. J. (2004). Error control coding (2nd ed.). Pearson.
19. Tian, C., Sasidharan, B., Aggarwal, V., Vaishampayan, V., & Kumar, P. (2015). Layered exact-repair regenerating codes via embedded error correction and block designs. IEEE Transactions on Information Theory, 61(4), 1933–1947. https://doi.org/10.1109/TIT.2015.2408595
20. Tianli, Z., & Chao, T. (2020). Fast erasure coding for data storage: a comprehensive study of the acceleration techniques. ACM Transactions on Storage, 16(1), 1.
21. Tsai, Q., Shao, E., Elston, J., & W, T. (2010). Prioritizing service requests on cloud with multi-tenancy. In IEEE 7th International Conference on E-Business Engineering (pp. 117–124). Shanghai, China: IEEE. https://doi.org/10.1109/ICEBE.2010.38
22. Tu, Y., Xiao, R., Han, Y., Chen, Y., Yu, D., & Yang, B. (2023). DDUC: an erasure-coded system with decoupled data updating and coding. Frontiers of Information Technology & Electronic Engineering, 24(5), 716–730. https://doi.org/10.1631/FITEE.2200466
23. Wu, X., Wang, Y., & Yan, Z. (2012). On algorithms and complexities of cyclotomic fast fourier transforms over arbitrary finite fields. IEEE Transactions on Signal Processing, 60(3), 1149–1158. https://doi.org/10.1109/TSP.2011.2178844
24. Xiao, Y., Zhou, S., & Zhong, L. (2020). Erasure coding-oriented data update for cloud storage: A survey. IEEE Access, 8, 227982–227998.
25. Zhang, X., Cai, Y., Liu, Y., Zhao, Y., Deng, M., Cui, B., & Hu, M. (2020). NADE: nodes performance awareness and accurate distance evaluation for degraded read in heterogeneous distributed erasure code-based storage. Journal of Supercomputing, 76(6), 4946–4975. https://doi.org/10.1007/s11227-019-02879-6
26. Zhen, H., Jinbang, C., Yisong, L., Pengfei, Y., & Yuxing, P. (2015). Minimizing data redundancy for high reliable cloud storage systems. Computer Networks, 81, 164–177. https://doi.org/10.1016/j.comnet.2015.02.013