Fractional Repetition Codes Based on Petersen Graphs

doi:10.3969/j.issn.1006-2475.2024.03.020

Abstract

Abstract: Abstract： In order to study the repair efficiency of distributed storage system， a fractional repetition code design based on Petersen graph edge coloring is proposed. The design uses the edge coloring of Petersen graph to construct， that is， the coloring the edges of Petersen graph is dyed first， the different number of colored edges is marked， and then the links of different edge colors in Petersen graph is constructed. Finally， each link is regarded as a storage node of partial repeat code， which is called PECBFR code. Theoretical analysis points out that the PECBFR code can randomy access the system storage capacity in reach. In addition， the experimental simulation results show that the proposed fractional repeat code construction algorithm based on Petersen graph edge coloring， compared with the reed-solomon codes and simple regenerative codes in distributed storage system， can quickly repair the faulty node when the system repairs the faulty node. Compared with common coding algorithms in distributed storage systems， the performance of repair locality， repair complexity and repair bandwidth overhead are greatly improved.

Key words: Key words： distributed storage, Petersen graph, edge coloring, fractional repetition code, repair

CLC Number:

TP391.9

YU Chun-lei1, 2, LIU Du-jin1, ZHU Hua-wei1, YANG Jia-rong3. Fractional Repetition Codes Based on Petersen Graphs[J]. Computer and Modernization, 2024, 0(03): 122-126.

References

［1］ SIDDIQA A， AHMAD K， ABDULLAH G. Big data storage technologies： A survey［J］. Frontiers of Information Technology & Electronic Engineering， 2017，18（8）：1040-1070.
［2］王宏，嵇绍国. 大数据分析的现实应用及发展趋势研究［J］. 信息网络安全， 2021（增刊1）：134-138.
［3］ MAZUMDAR S， SEYBOLD D， KRITIKOS K， et al. A survey on data storage and placement methodologies for cloud-big data ecosystem［J］. Journal of Big Data， 2019，6（1）：1-37.
［4］ LV Z， LI X M， LV H， et al. BIM big data storage in WebVRGIS［J］. IEEE Transactions on Industrial Informatics， 2019，16（4）：2566-2573.
［5］ LI R N， SONG T Y， MEI B， et al. Blockchain for large-scale internet of things data storage and protection［J］. IEEE Transactions on Services Computing， 2018，12（5）：762-771.
［6］谭凯中，秦勃，何亚文. 面向过程的海洋时空数据分布式存储与并行检索［J］. 中国海洋大学学报（自然科学版）， 2021，51（11）：94-101.
［7］王静，何亚锦，雷珂，等. 基于差集矩阵的部分重复码构造［J］. 电子与信息学报， 2022，44（11）：4025-4033.
［8］ YANG Y， ZHENG X H， GUO W Z， et al. Privacy-preserving smart IoT-based healthcare big data storage and self-adaptive access control system［J］. Information Sciences， 2019，479：567-592.
［9］ LIANG W， FAN Y K， LI K C， et al. Secure data storage and recovery in industrial blockchain network environments［J］. IEEE Transactions on Industrial Informatics， 2020，16（10）：6543-6552.
［10］ LEE O T， AKASH G J， KUMAR S D M， et al. Storage node allocation methods for erasure code-based cloud storage systems［J］. Arabian Journal for Science and Engineering， 2019，44（11）：9127-9142.
［11］ KNAUFT E， GOGGIN E J， RUOCHENG L I， et al. Automatically Removing Dependency on Slow Disks in a Distributed Storage System： U.S. Patent 10，168，942［P］. 2019-01-01.
［12］王静，王相隆，雷珂，等. 基于混合型正交表构造部分重复码［J］. 电子测量与仪器学报， 2021，35（11）：68-75.
［13］余春雷，王静，王秘，等. 图因子分解的部分重复码构造［J］. 中国科技论文， 2019，14（11）：1260-1264.
［14］ VAISHAMPAYAN V A. Lattice erasure codes of low rank with noise margins［C］// 2018 IEEE International Symposium on Information Theory （ISIT）. IEEE， 2018：961-965.
［15］ BALAJI S B， KRISHNAN M N， VAJHA M， et al. Erasure coding for distributed storage： An overview［J］. Science China Information Sciences， 2018，61（10）：1-45.
［16］王静，孙伟，何亚锦，等. 基于Hadamard矩阵构造部分重复码［J］. 电子科技大学学报， 2021，50（2）：173-179.
［17］沈克勤，孙伟，何亚锦，等. 基于矩阵变换和可调节环的部分重复码构造［J］. 计算机系统应用， 2020，29（12）：187-193.
［18］余春雷，王静，杨成福，等. 哈夫曼树的异构部分重复码构造［J］. 北京邮电大学学报， 2021，44（6）：116-121.
［19］ PAPAILIOPOULOS D S， DIMAKIS A G， CADAMBE V R. Repair optimal erasure codes through hadamard designs［J］. IEEE Transactions on Information Theory， 2017，59（5）：3021-3037.
［20］ GOPARAJU S， FAZELI A， VARDT A. Minimum storage regenerating codes for all parameters［J］. IEEE Transactions on Information Theory， 2017，63（10）：6318-6328.
［21］ KRALEVSKA K， GLIGOROSKI D， JENSEN R E， et al. Hashtag erasure codes： From theory to practice［J］. IEEE Transactions on Big Data， 2017，4（4）：516-529.
［22］朱兵，李挥，陈俊，等. 基于可分组设计的部分重复码研究［J］. 通信学报， 2015，36（2）：102-109.
［23］ ALRABIAH O， GURUSWAMI V. An exponential lower bound on the sub-packetization of minimum storage regenerating codes［J］. IEEE Transactions on Information Theory， 2021，67（12）：8086-8093.
［24］肖鹤玲，郭网媚，王静. 基于再生码的区块链分布式编码方案［J］. 吉林大学学报（工学版）， 2022，52（11）：2685-2697.
［25］ ZHU B. A study on universally good fractional repetition codes［J］. IEEE Communications Letters， 2018，22（5）：890-893.
［26］刘光军，熊金波，张力宁，等. 面向再生编码云存储的高效隐私保护审计方案［J］. 西南大学学报（自然科学版）， 2020，42（10）：37-45.
［27］ PORTER A， SILAS S， WOOTTERS M. Load-balanced fractional repetition codes［C］// 2018 IEEE International Symposium on Information Theory （ISIT）. IEEE， 2018：2072-2076.
［28］张曦，孙旭，郭晓虎，等. 面向GPU的非结构网格有限体积计算流体力学的图染色方法优化［J］. 国防科技大学学报， 2022，44（5）：24-34.
［29］余春雷，王娥，刘星，等. 图因子分解的故障节点快速修复［J］. 计算机系统应用， 2023，32（2）：394-399.
［30］余春雷. 分布式存储系统中数据存储研究［D］. 西安：长安大学， 2020.

[1]	ZHONG Jiaxuan1, LANG Xun1, ZHANG Ningtao2, ZHANG Zhao3, GUO Zhenyu2, ZHANG Mei2, ZHANG Yufeng1. Enhanced Detection and Evaluation of Facial Wrinkles Based on Image Denoising [J]. Computer and Modernization, 2024, 0(10): 35-41.
[2]	LI Wei1, HE Haobo1, LI Guang2, KUANG Lidan1, ZHANG Jin1. A Review of Bionic Olfactory Model Construction Methods and Applications [J]. Computer and Modernization, 2024, 0(10): 100-106.
[3]	ZHANG Gaoyi1, XU Yang1, 2, CAO Bin1, 3, LI Yifei3. 3D Visualization Monitoring System of Aluminum Reduction Cell Based on Digital Twin [J]. Computer and Modernization, 2024, 0(05): 104-109.
[4]	DU Han-yu, WEI Yan, TANG Bao-xiang, LIAO Heng-feng, YE Si-jia. Low-light Image Enhancement Based on Dual Attention Residual Blocks [J]. Computer and Modernization, 2024, 0(03): 85-91.