Abstract: As one of the most important basic problems in distributed computing, the consensus problem is widely used in the fields of state machine replication, atomic broadcast, leader election and so on. The algorithm for solving the consensus problem usually has the problems of single leader performance bottlenecks, response latency affected by command conflicts. In response to these problems, a low-latency consensus algorithm MEPaxos (modified Egalitarian Paxos) is proposed in asynchronous distributed systems under non-Byzantine failures. First, the method of calculating the system average latency is proposed. Then, a timeout mechanism is introduced to improve the two-phase commit algorithm. Later, based on the system average latency calculation result, an improved two-phase commit algorithm is used to automatically select an algorithm mode with a smaller average latency. Finally, this algorithm is compared with the current consensus algorithm experimentally on Amazon EC2 (elastic compute cloud) platform. The results show that the system latency performance has been improved using the MEPaxos algorithm.

Key words: distributed computing, consensus algorithm, low latency, Paxos

摘要： 共识问题作为分布式计算中最重要的基本问题之一，被广泛应用在状态机复制、原子广播、领导者选举等领域。解决共识问题的算法通常存在单领导者性能瓶颈、响应延迟受命令冲突的影响等问题。针对这些问题，在非拜占庭故障下的异步分布式系统中，提出了一种低延迟的共识算法MEPaxos（modified Egalitarian Paxos）。首先，提出了系统平均延迟的计算方法；然后，引入超时机制对二阶段提交算法进行改进；接着，根据系统平均延迟计算结果，利用改进的二阶段提交算法自动选择平均延迟较小的算法模式执行；最后，在亚马  逊弹性计算云（elastic compute cloud，EC2）平台上将此算法与当前共识算法进行实验对比分析，结果表明，MEPaxos算法下，系统延迟性能得到了提升。

关键词: 分布式计算, 共识算法, 低延迟, Paxos