Study On Distributed Computing Methods Based On Coding Techniques

Nowadays,distributed computing has become a common approach for large-scale computation of tasks due to benefits such as high reliability,scalability,computation speed,and cost-effectiveness.However,distributed computing faces critical issues related to straggler effects.In particular,a distributed computing network may include straggler nodes that run intermittently slower.This results in a longer overall time needed to execute the computation tasks,thereby limiting the performance of distributed computing.To address this issue,through a combination of coding theoretic techniques and distributed computing,coded distributed computing(CDC)has been recently proposed by scholars as a promising solution.And coding theoretic techniques have proved effective in Wi Fi and cellular systems to deal with channel noise.Therefore,CDC may significantly alleviate the effects of straggler nodes,provide fault-tolerance,privacy and security.However,for sparse matrix multipcation and distributed secure matrix multipcation problem,the “completion time” of existing coded distributed computing methods depend only on computing time of the fastest set of worker nodes,and without considering computing results of tasks completed by slow worker nodes(straggler nodes).In this thesis,a hierarchical coded sparse matrix multiplication computing method is proposed,and a distributed secure computing method using hierarchical code is designed.The main research results of the thesis are as follows:1.The basic model of coded distributed computing and an example of Coded Tera Sort that accelerates computation through coding are explained.Moreover,the polynomial coded matrix multiplication computing method is analyzed.The basic concepts and properties of entropy and mutual information are summarized.2.In the distributed sparse matrix multiplication problem,the completion time of the existing coded distributed computing methods depend only on the fastest set of worker nodes and do not fully consider computing results of straggler nodes.In order to reduce the completion time of computing tasks,by using computing results of straggler nodes,a hierarchical coded sparse matrix multiplication computing method is proposed.Simulation experiment results show that,compared with the existing coded sparse matrix multiplication computing scheme,the proposed sparse matrix multiplication computing scheme can reduce the completion time of computing tasks,and at the same time can maintain the advantages of the “near optimal recovery threshold” and linear decoding complexity.3.By using computing results of straggler nodes,a distributed secure computing method using hierarchical code is proposed.Simulation experiment resluts show that,compared with the existing distributed secure computing scheme using polynomial codes,the distributed secure computing scheme using hierarchical code can reduce the completion time of master node while maintaining the advantages of the optimal recovery threshold.