The Research Of Consensus Algorithms In Distributed Computing

Consensus algorithms are at the core of distributed computing,which mainly solve the problem how multiple computing nodes agree on the data value required during computation in the presence of failures.At present,Multi-Decree Paxos(Multi-Paxos)algorithm dominates the field of consensus algorithms.However,its design strategy of choosing a single leader not only has the risk of a single point of failure,but also affects the performance of the algorithm.In response to this design flaw,many Multi-Paxos algorithm variants have been proposed.Among them,Egalitarian Paxos(EPaxos)algorithm,which was proposed by Iulian Moraru et al.at the Twenty-Fourth ACM Symposium on Operating Systems Principles(SOSP 2013),has excellent performance and receives extensive attention in the industry.There is no leader in EPaxos,and all computing nodes can handle client commands.The performance of EPaxos is excellent when there is no conflict between client commands.However,the situation of client commands conflicting has an adverse impact on the performance.Based on EPaxos,the paper aims to improve the performance of consensus algorithms.The main research work and innovations are as follows:(1)Aiming at the problem that client commands conflicting affects the latency performance of EPaxos,a consensus algorithm,Modified Egalitarian Paxos(MEPaxos),is proposed by combining EPaxos algorithm with Multi-Paxos algorithm to achieve the goal of low latency.Firstly,considering the load condition of computing nodes,the real-time situation of the network and the processing situation of client commands,the method of calculating the system average latency is proposed.Then,the conversion algorithm is proposed based on the two-phase commit algorithm.Finally,according to the calculation results of the system average latency,the conversion algorithm is used to automatically select an algorithm mode with a lower system average latency.The theoretical analysis and experimental results show that the latency performance is improved under MEPaxos algorithm.(2)Aiming at the problem that client commands conflicting affects the performance of EPaxos,taking the latency performance and the throughput performance into account,a consensus algorithm,Partition Processing Egalitarian Paxos(PPEPaxos),is proposed based on EPaxos algorithm and the idea of partition processing.Firstly,the real-time monitoring system is designed to obtain the current processing status of client commands from each node and decide whether to perform partition processing.Then,the partition scheme decision algorithm is proposed to generate a specific partition scheme when partition processing is needed.Finally,inform each node of the partition scheme,and each node deals with client commands according to the partition scheme.The theoretical analysis and experimental results show that the lantency performance and the throughput performance are improved under PPEPaxos algorithm.(3)Compare MEPaxos and PPEPaxos and analyze the differences between them from both theoretical and experimental aspects.Firstly,analyze client commands processing flows of MEPaxos and PPEPaxos.Secondly,according to their client commands processing flows,combined with their detailed algorithm steps,theoretically analyze and compare MEPaxos and PPEPaxos from three aspects: the application scope,the latency performance and the throughput performance.Finally,the latency and throughput experiments are performed on MEPaxos and PPEPaxos to verify the results of theoretical analysis.