弓 婷，牛保宁，张栩豪

(太原理工大学 信息与计算机学院，山西 晋中 030600)

目前，Paxos[1]及其改进算法[2-9]已经被应用到全球式分布式系统[10-11]中。Multi-Paxos[12]是Paxos的改进算法之一，分两阶段执行，在第一阶段的准备阶段(Prepare phase)，发起共识请求的节点(proposer)广播被赋予唯一编号的提案。收到提案的节点(acceptors)判断当前提案的提案号是否最高，若是，则向proposer回复同意信息，否则不同意该提案。proposer获得多数(51%)acceptors同意后，被确定为Leader，进入第二阶段。回复同意信息的acceptors构成第一阶段Quorum(Q1).在第二阶段的接受阶段(Accept phase)，Leader将含有提案值的提案发送给acceptors.提案值获得多数acceptors同意后，对该提案值达成共识。回复同意提案值的acceptors构成第二阶段Quorum(Q2).Leader可以连续多次执行算法的第二阶段，确定多个命令。现有应用于广域网的分布式共识算法大多是以Multi-Paxos为基础。

在广域网中，分布式系统的节点被部署在各个不同的地理位置，通常以国家或地区为单位划分区域。Multi-Paxos的执行需要大量的跨区域通信，每个命令达成共识的延迟L由两部分构成：客户端与服务器节点(proposer或Leader)间的通信延迟Lc、服务器节点执行Multi-Paxos的延迟Le.由分析达成共识的过程可知，延迟最大的部分是Le.当系统中无固定Leader时，Le由第一阶段的延迟L1和第二阶段的延迟L2构成；当系统中有Leader时，Le主要由L2构成。减小共识延迟L的关键在于减小L1和L2.在此基础上，通过减小Lc可进一步减小L.

广域网中的通信代价是共识延迟的主要原因，Q1和Q2节点数量越少，L1和L2就越小。Quorum相交要求是保证算法安全性要求的关键，算法的安全性要求是指算法两阶段确定的提案值是唯一的。……