Distributed Reliable Coding Scheme Based on Triple Modular Redundancy
(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)
Abstract
Aiming at the problems of high system delay and low reliability caused by excessive data exchange in the Shuffle phase in traditional Coded Distributed Computing schemes, a TMR-CDC scheme is proposed. Firstly, the TMR-CDC model is created, which backs up the same data redundantly at different nodes, and reduces the amount of data transmission while ensuring that there is enough intermediate value to calculate the final result. Secondly, the verification mechanism is integrated into the data transmission process to detect the correctness of the calculation results, and the TMR-CDC algorithm is designed to implement the scheme. Finally, experiments show that the TMR-CDC scheme reduces the ratio of the running time of the Shuffle phase to the total running time of the Coded Distributed Computing from 34.53% of the C-CDC scheme and 33.27% of the S-CDC scheme to 26.39%. Moreover, the fault-tolerant mechanism set in the TMR-CDC scheme significantly improves the reliability of the system.
Keywords
Coded Distributed Computing; reliable coding; data shuffle; triple modular redundancy; communication load optimization
References
- [1] Zheng Tengfei, Zhou Tongqing, Cai Zhiping, etc A Review of Coding Computing Research [J]. Computer Research and Development, 2021, 58 (10): 2187-2221
- [2] ZHANG Z Y,CHERKASOVA L,LOO B T. Performance Modeling of MapReduce Jobs in Heterogeneous Cloud Environments [C]//2013 IEEE Sixth International Conference on Cloud Computing.Santa Clara:IEEE,2013:839-846.
- [3] LI S,MADDAH-ALI M A,AVESTIMEHR A S. Compressed Coded Distributed Computing [C]//2018 IEEE International Symposium on Information Theory (ISIT).Vail:IEEE,2018:2032-2036.
- [4] DEAN J,GHEMAWAT S. MapReduce: Simplified Data Processing on Large Clusters [J].Communications of the ACM,2008,51(1):107-113.
- [5] CHEN H N,LONG J F,MA S,et al. On the Optimality of Data Exchange for Master-aided Edge Computing Systems [J].IEEE Transactions on Communications,2023,71(3):1364-1376.
- [6] LI S,YU Q,MADDAH-ALI M A,et al. A Scalable Framework for Wireless Distributed Computing [J].IEEE/ACM Transactions on Networking,2017,25(5):2643-2654.
- [7] Dong Hongyan Research on Coding Distributed Computing Scheme Based on Group Copying [D]. Guilin: Guangxi Normal University, 2023
- [8] HORII S. Improved Computation-communication Trade-off for Coded Distributed Computing Using Linear Dependence of Intermediate Values [C]//2020 IEEE International Symposium on Information Theory (ISIT).Los Angeles:IEEE,2020:179-184.
- [9] LI S Z,YU Q,MADDAH-ALI M A,et al. A Scalable Coded Computing Framework for Edge-facilitated Wireless Distributed Computing [C]//2016 IEEE/ACM Symposium on Edge Computing(SEC).Washington:IEEE,2016:79-80.
- [10] PARRINELLO E,LAMPIRIS E,ELIA P. Coded Distributed Computing with Node Cooperation Substantially Increases Speedup Factors [C]//2018 IEEE International Symposium on Information Theory (ISIT).Vail:IEEE,2018:1291-1295.
- [11] EZZELDIN Y H,KARMOOSE M,FRAGOULI C. Communication vs Distributed Computation: An Alternative Trade-off Curve [C]//2017 IEEE Information Theory Workshop (ITW).Kaohsiung:IEEE,2017:279-283.
- [12] NG J S,LIM W Y B,LUONG N C,et al. A Survey of Coded Distributed Computing [J/OL].arXiv:2008.09048 [cs.DC].[2020-08-20].https://arxiv.org/abs/2008.09048.
- [13] LI S,MADDAH-ALI M A,AVESTIMEHR A S. Coded MapReduce [C]//2015 53rd Annual Allerton Conference on Communication,Control,and Computing (Allerton).Monticello:IEEE,2015:964-971.
- [14] JIANG J,WANG W,ZHOU L. Cascaded Coded Distributed Computing Schemes Based on Symmetric Designs [J].IEEE Transactions on Communications,2022,70(11): 7179-7190.
- [15] Li Weidong Research on Coding Distributed Computing Method for Matrix Vector Multiplication [D]. Nanjing: Nanjing University, 2020
- [16] Wang Yan, Li Nianshuang, Wang Xiling, etc Overview of Encoding Technology Improving the Performance of Large scale Distributed Machine Learning [J]. Computer Research and Development, 2020, 57 (3): 542-561
- [17] Zhang Ji, Xie Zaipeng, Mao Yingchi, etc Fault tolerant algorithm combining distributed coding computation under MapReduce framework [J]. Computer Engineering, 2021, 47 (4): 173-179
- [18] REISIZADEH A,PRAKASH S,PEDARSANI R,et al. Coded Computation Over Heterogeneous Clusters [J].IEEE Transactions on Information Theory,2019,65(7): 4227-4242.
- [19] LEDMI A,BENDJENNA H,HEMAM S M. Fault tolerance in Distributed Systems: A Survey [C]//2018 3rd International Conference on Pattern Analysis and Intelligent Systems (PAIS).Tebessa:IEEE,2018:1-5.
- [20] Wang Qiang, Yuan Youguang Research on High Performance Fault Tolerant Processing Core [J]. Computer and Digital Engineering, 2000 (3): 5-11
- [21] LYONS R E,VANDERKULK W. The Use of Triple-modular Redundancy to Improve Computer Reliability [J].IBM Journal of Research and Development,1962,6(2):200-209.
- [22] Ji Shengpeng Coding distributed computing scheme based on fewer output functions and primary/auxiliary compression [D]. Guilin: Guangxi Normal University, 2023
- [23] LI X,LIN Y. A Triple Modular Eager Redundancy Fault Tolerant Technique for Distributed Stream Architecture [J].Computer Engineering and Science,2015,37(12):2233.
- [24] Pang Bo Research on Distributed Encoding Computing Offloading Strategy for Star Earth Fusion Network [D]. Harbin: Harbin Institute of Technology, 2021
- [25] Yuan Yanfei Research on Distributed Computing Methods Based on Encoding Technology [D]. Xi'an: Xi'an University of Electronic Science and Technology, 2021
Funding
Key Research and Development Program Fund of Gansu Province (20YF8GA123)
About the authors
Zhao Shuxu (1976-), male, Han nationality, from Qingdao, Shandong Province, professor, doctor, research direction: intelligent transportation, edge computing; Li Xuefei (1997-), male, Han nationality, from Dingxi, Gansu Province, master degree candidate, research direction: coding distributed computing, edge computing; Wang Xiaolong (1989-), male, Han nationality, from Dingxi, Gansu Province, lecturer, doctor, research direction: edge alliance, edge computing.