Article Details

Title · Authors · Abstract · Keywords · DOI · References

Distributed Reliable Coding Scheme Based on Triple Modular Redundancy

ZHAO Shuxu, LI Xuefei, WANG Xiaolong

(School of Electronic and Information Engineering, Lanzhou Jiaotong University, Lanzhou 730070, China)

Section:Computer Technology · 2025, Vol. 9, No. 11 · Pages:70-77 · 2096-4706(2025)11-0070-08 · CLC number:TP393 · Document code:A · DOI:10.19850/j.cnki.2096-4706.2025.11.014

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. [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. [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. [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. [4] DEAN J,GHEMAWAT S. MapReduce: Simplified Data Processing on Large Clusters [J].Communications of the ACM,2008,51(1):107-113.
  5. [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. [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. [7] Dong Hongyan Research on Coding Distributed Computing Scheme Based on Group Copying [D]. Guilin: Guangxi Normal University, 2023
  8. [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. [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. [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. [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. [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. [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. [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. [15] Li Weidong Research on Coding Distributed Computing Method for Matrix Vector Multiplication [D]. Nanjing: Nanjing University, 2020
  16. [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. [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. [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. [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. [20] Wang Qiang, Yuan Youguang Research on High Performance Fault Tolerant Processing Core [J]. Computer and Digital Engineering, 2000 (3): 5-11
  21. [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. [22] Ji Shengpeng Coding distributed computing scheme based on fewer output functions and primary/auxiliary compression [D]. Guilin: Guangxi Normal University, 2023
  23. [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. [24] Pang Bo Research on Distributed Encoding Computing Offloading Strategy for Star Earth Fusion Network [D]. Harbin: Harbin Institute of Technology, 2021
  25. [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.