少數(shù)決：更安全的分布式一致性算法選舉機(jī)制*

李 彬，姜建國(guó)

1.北京交通大學(xué)計(jì)算機(jī)與信息技術(shù)學(xué)院，北京 100044

2.國(guó)家保密科技測(cè)評(píng)中心，北京 100044

3.中國(guó)科學(xué)院信息工程研究所，北京 100093

1 引言

現(xiàn)實(shí)生活中，選舉就是讓符合多數(shù)人想法或利益的人獲得領(lǐng)導(dǎo)權(quán)，被選舉者需要大多數(shù)人或大多數(shù)有投票權(quán)人的贊同，即多數(shù)者決策。這個(gè)在人類(lèi)社會(huì)中的民主模式啟發(fā)并影響了分布式系統(tǒng)一致性算法研究者們，經(jīng)典的一致性算法Paxos的選舉機(jī)制就是如此。它的Leader選舉分為兩個(gè)階段[1]，且兩個(gè)階段無(wú)法分割、相互關(guān)聯(lián)共同保障了數(shù)據(jù)的一致性。第一階段：準(zhǔn)備階段，提案者（proposer）選擇一個(gè)提案號(hào)，并發(fā)送提案給投票者（acceptor），試探能否得到多數(shù)派投票者的響應(yīng)。第二階段：如果某個(gè)提案者在第一階段收到多數(shù)派投票者的響應(yīng)，則提交提案，如果能夠再次得到多數(shù)派acceptor的同意，則這個(gè)提案者被選為L(zhǎng)eader。顯然，這兩個(gè)階段都是采用多數(shù)決的方式。其實(shí)，分布式系統(tǒng)中各個(gè)服務(wù)器并不在乎Leader是誰(shuí)，Leader是否意識(shí)形態(tài)與自己一致，是否為民主選舉，他們需要的只是能非固定地選出一個(gè)服務(wù)器，它能按照協(xié)議履行相關(guān)職能，讓系統(tǒng)保持?jǐn)?shù)據(jù)更新一致。本文將提出“少數(shù)決”這一新的選舉機(jī)制，通過(guò)研究分析此種選舉不僅是簡(jiǎn)單的逆向思維，還在保護(hù)去中心化，提高一致性算法安全性上有更好的表現(xiàn)。

2 基于選舉的一致性算法面臨的風(fēng)險(xiǎn)

首先，Multi-Paxos[2]、Raft[3]、ZAB[4]、VR（viewstamped replication）[5]這些已實(shí)際應(yīng)用的一致性算法其實(shí)都是基于選舉的一致性算法。Multi-Paxos中的Leader是作為對(duì)經(jīng)典Paxos的優(yōu)化而提出，通過(guò)選擇一個(gè)proposer作為L(zhǎng)eader降低多個(gè)提案者引起沖突的概率，提升性能將一次決議的平均消息代價(jià)縮小到最優(yōu)的兩次，而且當(dāng)有多個(gè)Leader存在時(shí)算法也仍是安全的，只是退回為經(jīng)典Paxos選舉。而Raft、ZAB、VR這些強(qiáng)調(diào)唯一Leader的協(xié)議，它們直接從Leader的角度描述協(xié)議的流程，但是實(shí)際上它們使用了和Paxos完全一樣的原理來(lái)保證協(xié)議的安全性，當(dāng)同時(shí)存在多個(gè)節(jié)點(diǎn)同時(shí)嘗試成為L(zhǎng)eader或者多個(gè)節(jié)點(diǎn)都認(rèn)為自己是Leader時(shí)，它們也將退回至經(jīng)典Paxos選舉[6]。

在基于選舉的分布式系統(tǒng)中可能存在這么一種問(wèn)題節(jié)點(diǎn)：它們不同于傳統(tǒng)的拜占庭將軍問(wèn)題[7]（Byzantine failures）節(jié)點(diǎn)，不會(huì)故意發(fā)出錯(cuò)誤的更新去破壞系統(tǒng)數(shù)據(jù)的一致性，但是它們會(huì)在選舉誰(shuí)作為L(zhǎng)eader時(shí)操作選票，目的是讓指定的節(jié)點(diǎn)獲得Leader特權(quán)，從而壟斷客戶業(yè)務(wù)。這種自私行為本身違背了去中心的原則，一旦這個(gè)被指定的節(jié)點(diǎn)遭受攻擊或故障，將是災(zāi)難性的系統(tǒng)崩潰。因此，需要選擇更安全的一致性算法選舉機(jī)制來(lái)提升整個(gè)分布式系統(tǒng)的安全性。

3 現(xiàn)實(shí)中的少數(shù)決選舉

現(xiàn)實(shí)中少數(shù)決選舉來(lái)源于Liar Game中的Minority Decision[8]，它并不牽扯少數(shù)者博弈[9]問(wèn)題，本是一個(gè)純粹基于隨機(jī)目的選擇“幸運(yùn)兒”游戲，具體規(guī)則如下：

首先，組織者隨機(jī)選擇一名參與者出一道二選一的題目，如“你是否喜歡紅色？”。為充分保證公平性，一般是一人出一題后就換下一個(gè)人出題，出題順序無(wú)特殊要求，總之大家都有公平的機(jī)率出題即可。

接著，大家根據(jù)題目和自己想法做出“是”或“否”的選擇。這里需要說(shuō)明的是大家的選擇并不一定是自己真實(shí)的想法，需要思考是：怎么讓自己的選擇不是大多數(shù)人的選擇？但可以肯定的是絕不能讓別人知道你的選擇，因?yàn)槿绻腥酥雷銐蚨嗳说倪x擇后，他就能做出少數(shù)選擇。因此，現(xiàn)實(shí)中最簡(jiǎn)單的方法就是將選擇寫(xiě)在紙上后折疊，再投入一個(gè)不透明的箱子中。

一次選舉包含多輪答題，每輪答題結(jié)束后，由組織者唱票。選擇為少數(shù)派的那一方獲勝，進(jìn)入下一輪繼續(xù)進(jìn)行出題、答題；而選擇為多數(shù)派一方遭淘汰；如雙方人數(shù)持平或大家選擇都一致，則無(wú)淘汰者，并直接進(jìn)入下一輪。

最后，可能是剩下一個(gè)人或是兩個(gè)人，一個(gè)人時(shí)直接宣布勝出；兩個(gè)人時(shí)則組織者參與進(jìn)來(lái)以打破兩人無(wú)法產(chǎn)生少數(shù)派的僵局，進(jìn)行決賽。假設(shè)進(jìn)入決賽的兩人為A和B，組織者為Z。如果不是A或B的選擇為少數(shù)派（即Z勝出），則A、B和Z繼續(xù)下一輪，直至A或B勝出。

根據(jù)上述規(guī)則描述，可以歸納此種選舉機(jī)制的流程如圖1所示。

Fig.1 Minority election mechanism process圖1 少數(shù)決選舉機(jī)制流程

下面舉例進(jìn)行說(shuō)明，假設(shè)參與者為10人，分別為P1,P2,…,P10，組織者為Z。例1：第一輪P1、P2、P3、P4選擇Yes，其余人選擇No，則P1、P2、P3、P4進(jìn)入下一輪；第二輪P1、P2、P3選擇Yes，P4選擇No，則P4獲勝。例2：第一輪P1、P2選擇Yes，其余人選擇No，則P1、P2進(jìn)入下一輪（決賽）；第二輪P1、P2選擇Yes，Z選擇No，則無(wú)人淘汰進(jìn)行下一輪；第三輪P1和Z選擇Yes，P2選擇No，則P2獲勝。例3：第一輪P1、P2、P3、P4、P5選擇Yes，其余人選擇No，平局無(wú)人淘汰進(jìn)行下一輪；第二輪P1選擇Yes，其余人選擇No，則P1獲勝。

4 安全性分析

多數(shù)決選舉中最常見(jiàn)的一種作弊方式就是控票，控制半數(shù)以上有投票權(quán)的人的選票，就能保證自己想讓誰(shuí)當(dāng)選就讓誰(shuí)當(dāng)選。在經(jīng)典Paxos中可以更容易些，因?yàn)橹挥衋cceptor（投票者）能投票，所以只要控制50%以上的acceptor就能隨心所欲地指定Leader。而在類(lèi)Raft這種每個(gè)節(jié)點(diǎn)都有投票權(quán)的系統(tǒng)中實(shí)現(xiàn)控票，則需要控制50%以上的節(jié)點(diǎn)。本章將分析采用少數(shù)決選舉機(jī)制是否也存在類(lèi)似的安全性問(wèn)題。為方便分析，本章假設(shè)是由22個(gè)參與者組成的少數(shù)決選舉系統(tǒng)。

4.1 絕對(duì)控制攻擊

在這22個(gè)參與者組成的少數(shù)決選舉系統(tǒng)中，如果已經(jīng)控制了其中的12個(gè)參與者的選票（超過(guò)50%），接下來(lái)是否能夠完全按照自己的意志選擇Leader。假設(shè)P1,P2,…,P22為22個(gè)參與者，P1,P2,…,P12組成受控團(tuán)隊(duì)。假定想指定P1成為L(zhǎng)eader，就必須保證P1能100%順利通過(guò)3輪的淘汰，因此團(tuán)隊(duì)采取全力保證P1和盡可能多的隊(duì)友進(jìn)入下一輪的方式進(jìn)行投票。第一輪，因?yàn)檫€是不知道團(tuán)隊(duì)外這10個(gè)參與者的選擇，所以要保證P1能進(jìn)入第二輪，只能讓P2,P3,…,P12這11個(gè)隊(duì)友選擇Yes，P1選擇No，這樣才能保證結(jié)果最壞是平票（因?yàn)橛锌赡軋F(tuán)隊(duì)外的10個(gè)參與者也同時(shí)選擇No），但只要這10個(gè)參與者是未經(jīng)商量隨機(jī)投票的，總會(huì)有一輪它們會(huì)選擇不同的答案。但是，這樣做后第二輪又變成公平的10選1選舉了，P1將只有10%的獲勝幾率。

加大攻擊力度，分析在控票率達(dá)到81.8%（18/22）的情況下是否可以保證P1獲勝。第一輪，因?yàn)椴恢缊F(tuán)隊(duì)外P19、P20、P21、P22的選擇，所以要保證P1能進(jìn)入下一輪，先能讓P1,P2,…,P7這7個(gè)隊(duì)友選擇Yes，P8,P9,…,P18這11個(gè)隊(duì)友選擇No，這樣才能保證結(jié)果最壞是平票（P19、P20、P21、P22同時(shí)選擇Yes），但只要P19、P20、P21、P22是未經(jīng)商量隨機(jī)投票的，總會(huì)有一輪其中會(huì)有參與者因選擇No而遭淘汰。假設(shè)第一輪P20、P21、P22選擇Yes，P19選擇No，因此P1,P2,…,P7和P20、P21、P22進(jìn)入下一輪。第二輪，同理P1、P2這2個(gè)隊(duì)友選擇Yes，P3、P4、P5、P6、P7這5個(gè)隊(duì)友選擇No，最壞情況，假設(shè)第二輪P21、P22選擇Yes，P20選擇No，因此P1、P2和P21、P22進(jìn)入下一輪。第三輪，P1、P2無(wú)論怎么作弊，都無(wú)法保證P1獲勝。這表示控制81.8%的選票只能將P1獲勝的幾率提升至25%，且其他少于18個(gè)隊(duì)友的團(tuán)隊(duì)也都無(wú)法保證P1的100%獲勝。

再次加大攻擊力度，分析在控票率達(dá)到86.4%（19/22）的情況下是否可以保證P1獲勝。第一輪，因?yàn)椴恢缊F(tuán)隊(duì)外P20、P21、P22的選擇，所以要保證P1能進(jìn)入下一輪，先能讓P1,P2,…,P8這8個(gè)隊(duì)友選擇Yes，P9,P10,…,P19這11個(gè)隊(duì)友選擇No，這樣才能保證結(jié)果最壞是平票（P20、P21、P22也選擇Yes），但只要P20、P21、P22是未經(jīng)商量隨機(jī)投票的，總會(huì)有一輪其中會(huì)有參與者因選擇No而遭淘汰。假設(shè)第一輪P21和P22選擇Yes，P20選擇No，因此P1,P2,…,P8和P21、P22進(jìn)入下一輪。第二輪，同理P1、P2、P3這3個(gè)隊(duì)友選擇Yes，P4,P5,…,P8這5個(gè)隊(duì)友選擇No，這時(shí)最壞情況又是平票，逼P21和P22至少一個(gè)淘汰，否則永遠(yuǎn)平票。假設(shè)P22選擇Yes，P21選擇No，因此P1、P2、P3和P22進(jìn)入下一輪。第三輪，同理P1選擇Yes，P2、P3這2個(gè)隊(duì)友選擇No，P22注定被淘汰，而P1通過(guò)一系列操作終于獲勝了。

根據(jù)上面分析可以得出，少數(shù)決中絕對(duì)控制攻擊需要滿足一個(gè)十分苛刻的條件才能確保攻擊成功，表1列出了參與者分別為3至30個(gè)時(shí)保證絕對(duì)控制攻擊成功所需要的受控個(gè)數(shù)，圖2展示了對(duì)應(yīng)的所需受控率。

Table 1 Number of controls required for success of absolute control attack with 3 to 30 participants表1 參與者為3至30個(gè)時(shí)絕對(duì)控制攻擊成功所需受控?cái)?shù)

分析表1和圖2，可以看出：

（1）參與者為4個(gè)時(shí)，控票率達(dá)到75%（3/4）時(shí)，是少數(shù)決遭受絕對(duì)控制攻擊所需控票率的最低值，即最易受攻擊狀態(tài)；

（2）參與者為10個(gè)時(shí)，是一個(gè)低值（下劃線標(biāo)記的），此時(shí)控票率需達(dá)到80%（8/10）；

（3）參與者為22個(gè)時(shí)，是另一低值，此時(shí)控票率需達(dá)到86.4%（19/22）；進(jìn)而推論隨著參與者的增加，低值出現(xiàn)的頻率將越來(lái)越低，且低值也越來(lái)越高，即攻擊難度越來(lái)越大。

4.2 團(tuán)隊(duì)攻擊

Fig.2 Control rate required for success of absolute control attack with 3 to 30 participants圖2 參與者為3至30個(gè)時(shí)絕對(duì)控制攻擊成功所需受控率

如果能成功控制一定數(shù)量節(jié)點(diǎn)的投票，是可以保證這個(gè)團(tuán)隊(duì)中的一個(gè)最終獲勝，即團(tuán)隊(duì)攻擊成功。第一輪中，安排團(tuán)隊(duì)中的8個(gè)節(jié)點(diǎn)中4個(gè)節(jié)點(diǎn)選Yes，另4個(gè)節(jié)點(diǎn)選No。因此這一輪后留下來(lái)的節(jié)點(diǎn)中總有團(tuán)隊(duì)中的4個(gè)，最壞情況下還有4個(gè)團(tuán)隊(duì)外的節(jié)點(diǎn)。第二輪中，安排團(tuán)隊(duì)中的4個(gè)隊(duì)友中2個(gè)選Yes，另2個(gè)選No。因此這一輪后留下來(lái)的節(jié)點(diǎn)中總有團(tuán)隊(duì)中的2個(gè)，最壞情況下還有2個(gè)團(tuán)隊(duì)外的節(jié)點(diǎn)。第三輪中，團(tuán)隊(duì)中的2個(gè)隊(duì)友中的1個(gè)選Yes，另1個(gè)選No，只要另外兩節(jié)點(diǎn)是未經(jīng)商量隨機(jī)投票的，總會(huì)有一輪它們選擇同樣的答案，于是最終成為L(zhǎng)eader將是團(tuán)隊(duì)中的一員。

要保證在少數(shù)決選舉團(tuán)隊(duì)攻擊成功，團(tuán)隊(duì)成員的數(shù)量Tn要滿足一定條件。Tn與可能進(jìn)行的有效投票輪數(shù)r（平局輪不計(jì)，r與參與者總數(shù)An相關(guān)）有關(guān)，因此當(dāng)控制節(jié)點(diǎn)數(shù)量Tn滿足Tn≥2r時(shí)可以確保團(tuán)隊(duì)攻擊成功。

但是，團(tuán)隊(duì)攻擊只能保證團(tuán)隊(duì)中的某一個(gè)成員被選為L(zhǎng)eader，但仍然無(wú)法確定最終獲勝的是哪一個(gè)，即只是縮小了產(chǎn)生Leader的節(jié)點(diǎn)范圍，降低了系統(tǒng)去中心化的程度。

4.3 欺詐攻擊

首先，假設(shè)P1找到P2,P3,…,P8等7個(gè)參與者在不為人知的情況下組成一個(gè)團(tuán)隊(duì)，把保證團(tuán)隊(duì)獲勝的方法告訴團(tuán)隊(duì)成員，并承諾團(tuán)隊(duì)獲勝后平分作為L(zhǎng)eader的權(quán)益。然后，P1再找P9,P10,…,P15等7個(gè)參與者秘密地組建第二支團(tuán)隊(duì)，策略和承諾相同。最后，P1再與剩余的P16,P17,…,P22秘密地組成第三支團(tuán)隊(duì)。這里成功地組織了3支“8人”團(tuán)隊(duì)，讓每個(gè)參與者都堅(jiān)信自己身在一個(gè)將要利用必勝法獲勝并平分勝利果實(shí)的團(tuán)隊(duì)里。除了P1，大家都不知道還有其他團(tuán)隊(duì)存在。在第一輪游戲中，P1指示每個(gè)團(tuán)隊(duì)里包括P1自己在內(nèi)的4個(gè)隊(duì)友投Yes，其余的人都投No。這樣下來(lái)，投Yes的一共就有10票，No有12票，于是P1和每個(gè)團(tuán)隊(duì)里除P1之外的另外3個(gè)人獲勝。下一輪游戲中，P1再指示每個(gè)隊(duì)伍里包括P1在內(nèi)的2人投Yes，其他人都投No，這樣Yes就有4票，No有6票，P1再次勝出。最后，P1自己投Yes，并指示其他人都投No，這就保證了P1可以100%獲勝。

這種攻擊方式因其在現(xiàn)實(shí)中確實(shí)存在理論上的可能，但在沒(méi)有獎(jiǎng)勵(lì)機(jī)制、沒(méi)有智能協(xié)商、需要重復(fù)多次選舉的分布式系統(tǒng)中是不可能實(shí)現(xiàn)的，因?yàn)榘岩恢滦运惴ó?dāng)作共識(shí)機(jī)制的分布式系統(tǒng)，被設(shè)定是不存在拜占庭將軍問(wèn)題的。

5 少數(shù)決在一致性算法中的實(shí)現(xiàn)

本文認(rèn)為可以利用少數(shù)決選舉的科學(xué)性產(chǎn)生一致性算法中的隨機(jī)Leader。通常來(lái)講，一個(gè)正確的一致性算法需要滿足以下3條性質(zhì)：

安全性：具備安全性的算法保證壞的事情絕對(duì)不會(huì)發(fā)生，例如分布式Leader選舉算法，絕對(duì)不會(huì)出現(xiàn)一個(gè)以上進(jìn)程被選為L(zhǎng)eader的情況。

存活性：具備存活性的算法保證好的事情終將發(fā)生，即算法在有限的時(shí)間內(nèi)可以結(jié)束。

去中心性：在去中心化系統(tǒng)中，任何人都是一個(gè)節(jié)點(diǎn)，任何人也都可以成為一個(gè)中心。任何中心都不是永久的，而是階段性的，任何中心對(duì)節(jié)點(diǎn)都不具有強(qiáng)制性[10]。

作為一致性算法中最關(guān)鍵的選舉機(jī)制設(shè)計(jì)也應(yīng)具備上述3個(gè)性質(zhì)，下面將給出少數(shù)決選舉機(jī)制的一個(gè)設(shè)計(jì)方案。

5.1 去中心化

因?yàn)榉植际较到y(tǒng)是去中心化的，所以不能固定設(shè)置一個(gè)組織者角色。另外，由組織者承擔(dān)出題者的職能是沒(méi)有任何問(wèn)題的，因此組織者可以是由所有節(jié)點(diǎn)輪流承擔(dān)，即每進(jìn)行一輪就換一個(gè)組織者，避免中心化的問(wèn)題。這種輪換機(jī)制，可以是簡(jiǎn)單地按ID號(hào)i從小到大順序輪轉(zhuǎn)，然后最大號(hào)碼鏈接1號(hào)的方式，即1 →2 →3 →…→max→1 →2…，也可以采用其他輪換機(jī)制。

5.2 統(tǒng)計(jì)參與者范圍

采取少數(shù)決選舉分布式系統(tǒng)的每個(gè)節(jié)點(diǎn)是需要知道整個(gè)系統(tǒng)節(jié)點(diǎn)個(gè)數(shù)An，之后增加或減少節(jié)點(diǎn)個(gè)數(shù)時(shí)要及時(shí)更新An，并且設(shè)置初始化判斷勝負(fù)的關(guān)鍵計(jì)數(shù)器n=An。

5.3 題目及計(jì)票方式

根據(jù)第3章描述的少數(shù)決選舉特點(diǎn)，題目并不要求難度只是需要二選一的題目，這就自然而然讓布爾值成為首選。而題目競(jìng)猜也可轉(zhuǎn)變?yōu)椋翰露M(jìn)制隨機(jī)數(shù)的最后一位、域名服務(wù)器ping值的奇偶性等方式。只要是能夠產(chǎn)生具有隨機(jī)性的布爾值，且布爾值出現(xiàn)的概率為50%的方式[11]均可作為少數(shù)決的題目。下面將以猜二進(jìn)制隨機(jī)數(shù)的最后一位為例進(jìn)行描述。

如由An個(gè)節(jié)點(diǎn)組成的分布式系統(tǒng)，每個(gè)節(jié)點(diǎn)產(chǎn)生一個(gè)隨機(jī)數(shù)Rn，并將自己ID信息Answ(Rn,i)一同發(fā)送給組織者，組織者將使用Lr(i)函數(shù)剝離i所對(duì)應(yīng)隨機(jī)數(shù)二進(jìn)制格式時(shí)的最后一位。需按照式（1）計(jì)算j，如果j=n/2、j=n或j=0則表示沒(méi)有淘汰者，每個(gè)節(jié)點(diǎn)重新產(chǎn)生隨機(jī)數(shù)；j＞n/2則Lr(i)=0對(duì)應(yīng)的節(jié)點(diǎn)ID號(hào)進(jìn)入下一輪比賽名單，設(shè)n=n-j；否則，Lr(i)=1對(duì)應(yīng)的節(jié)點(diǎn)ID號(hào)進(jìn)入下一輪比賽名單，設(shè)n=j。

5.4 存活性

少數(shù)決選舉的存活性問(wèn)題，就是Leader可以在有限的時(shí)間內(nèi)選舉出來(lái)，進(jìn)而推論就是二選一答題是否可以在有限次數(shù)內(nèi)結(jié)束。顯然，少數(shù)決選舉中的二選一答題問(wèn)題相當(dāng)于擲硬幣問(wèn)題。利用高斯分布函數(shù)[12]式（2），可得出以下結(jié)論：當(dāng)觀測(cè)結(jié)果的正面向上次數(shù)遠(yuǎn)遠(yuǎn)大于正面向下次數(shù)，也遠(yuǎn)遠(yuǎn)大于先驗(yàn)分布[13]的正面向下次數(shù)，則判斷下次為正面向上的概率無(wú)限接近1[14]。

式中，a、b、m、l分別代表先驗(yàn)分布的正面向上次數(shù)、反面向上次數(shù)、已觀測(cè)數(shù)據(jù)的正面向上次數(shù)、反面向上次數(shù)。

上述結(jié)論說(shuō)明了，隨著答題次數(shù)的增加，每個(gè)答題者的答案會(huì)一直變動(dòng)，極小概率會(huì)出現(xiàn)所有人答題結(jié)果都一致或結(jié)果永遠(yuǎn)是50%對(duì)50%的情況。因?yàn)樾「怕适录梢暈椴豢赡苁录?，所以二選一答題可以在有限次數(shù)內(nèi)結(jié)束。

5.5 組織者的期號(hào)

為避免由于通信延遲、重發(fā)等原因造成一個(gè)少數(shù)決系統(tǒng)中出現(xiàn)兩個(gè)或者兩個(gè)以上的組織者，造成混亂，每個(gè)組織者都需要附加一個(gè)期號(hào)（term）。這里的期號(hào)使用可參考Raft算法中的實(shí)現(xiàn)方式[3]，每次輪換組織者期號(hào)就會(huì)遞增，答題者只跟隨期號(hào)大的組織者進(jìn)行持續(xù)競(jìng)選。

5.6 組織者

組織者只需要接收本輪比賽名單內(nèi)的答題者的答案，初始名單為所有節(jié)點(diǎn)。組織者需要通知大家本輪答題開(kāi)始，讓答題者將隨機(jī)數(shù)Rn發(fā)送給自己。這個(gè)通知信息包含自己的期號(hào)和下一任組織者的ID信息，如M1(term,NextqwID)。

5.7 信息保密性和身份認(rèn)證

可以通過(guò)非對(duì)稱(chēng)加密算法[15]保證答題者隨機(jī)數(shù)的保密性和確認(rèn)答題者、組織者身份。非對(duì)稱(chēng)加密算法實(shí)現(xiàn)保密信息交換的基本過(guò)程是：每個(gè)節(jié)點(diǎn)生成一對(duì)密鑰并將公鑰公開(kāi)；當(dāng)答題者需要向組織者發(fā)送信息的時(shí)候使用組織者的公鑰對(duì)隨機(jī)數(shù)信息進(jìn)行加密后再發(fā)送給組織者；組織者再用自己私鑰對(duì)加密后的信息進(jìn)行解密。此外，非對(duì)稱(chēng)加密算法實(shí)現(xiàn)身份認(rèn)證的基本過(guò)程是：答題者可以使用自己的私鑰對(duì)需要發(fā)送的信息進(jìn)行簽名后再發(fā)送給組織者；組織者再用答題者的公鑰對(duì)答題者發(fā)送回來(lái)的數(shù)據(jù)進(jìn)行驗(yàn)簽，確認(rèn)其身份。

反之，組織者給答題者發(fā)送信息的加密方式和組織者的身份認(rèn)證也將采取上述方式，這里不再贅述。

5.8 唱票方式

組織者需要將期號(hào)、計(jì)票結(jié)果、進(jìn)入下一輪的節(jié)點(diǎn)ID號(hào)、本輪每個(gè)答題者的答案等信息，如M2(term,result,NRA_IDs,Answs(n)) 通過(guò)廣播方式告知本輪的每個(gè)答題者，以示公允。

M2中的信息越詳細(xì)越能體現(xiàn)公正性，因?yàn)槊總€(gè)答題者是可以通過(guò)M2發(fā)現(xiàn)當(dāng)前組織者是否有篡改答題結(jié)果或計(jì)票錯(cuò)誤等作惡行為。這里不必采取冷酷策略，即發(fā)現(xiàn)某組織者出現(xiàn)一點(diǎn)兒錯(cuò)誤就終止其參與資格，因?yàn)榭赡軙?huì)無(wú)法區(qū)分主觀作惡和客觀網(wǎng)絡(luò)傳輸錯(cuò)誤?？赏ㄟ^(guò)EigenTrust[16]、PeerTrust[17]等網(wǎng)絡(luò)節(jié)點(diǎn)信任評(píng)價(jià)方法，對(duì)該惡意節(jié)點(diǎn)做出臨時(shí)屏蔽或永久去除等懲罰措施。

5.9 容錯(cuò)處理

在少數(shù)決選舉進(jìn)行的過(guò)程中，可能會(huì)出現(xiàn)一些故障，如節(jié)點(diǎn)宕機(jī)或通信受阻的情況，下面描述兩種最常見(jiàn)故障的處理方式。

（1）答題者中途宕機(jī)。由于答題者可能宕機(jī)或通信受阻，在規(guī)定時(shí)間內(nèi)收到的答案?jìng)€(gè)數(shù)num(Answs)少于2個(gè)時(shí)，代表整個(gè)系統(tǒng)出現(xiàn)嚴(yán)重故障，本次選舉終止，按照ID號(hào)輪換下一個(gè)節(jié)點(diǎn)繼續(xù)出題；如果num(Answs)大于2個(gè)但少于預(yù)期個(gè)數(shù)n時(shí)，重置n(n=num(Answs))；如果計(jì)票結(jié)果為平票時(shí)，本輪無(wú)淘汰節(jié)點(diǎn)，直接進(jìn)行下一輪答題；如果計(jì)票結(jié)果可以分出勝負(fù)時(shí)，將未收到答案的答題者列為淘汰方，獲勝者繼續(xù)進(jìn)行下一輪答題。

（2）組織者中途宕機(jī)。答題者在發(fā)送一個(gè)答案給組織者后，一定時(shí)間內(nèi)未收到組織者的計(jì)票結(jié)果時(shí)，首先詢問(wèn)查看組織者狀態(tài)，如果確認(rèn)是組織者宕機(jī)且下一任組織者不是自己，就等待下一任組織者的廣播信息，準(zhǔn)備下一次答題；如果自己是下一任組織者，累加期號(hào)后廣播自己成為組織者的消息，準(zhǔn)備出題。

5.10 決賽問(wèn)題

按照現(xiàn)實(shí)中的游戲規(guī)則，決賽是需要組織者這個(gè)固定角色參與的，但在前面去中心化設(shè)計(jì)并已去掉了這個(gè)固定的角色的情況下，可以通過(guò)另一種方法解決此事。首先對(duì)比兩個(gè)節(jié)點(diǎn)ID號(hào)i1和i2，如果i1＞i2，則Mid=i1，Lid=i2；如果i1＜i2，則Mid=i2，Lid=i1。再對(duì)比兩個(gè)節(jié)點(diǎn)的答案Lr(i1)和Lr(i2)，如果決賽兩節(jié)點(diǎn)的答案是相同的，即“11”或“00”，就判定Lid對(duì)應(yīng)的那個(gè)節(jié)點(diǎn)當(dāng)選；如果是不同的，即“01”或“10”，就判定Mid對(duì)應(yīng)的那個(gè)節(jié)點(diǎn)當(dāng)選，這樣依然能夠保證Leader選舉的隨機(jī)性和公正性，形式化后的計(jì)算公式如式（3）所示。

5.11 組織者核心算法偽代碼

6 實(shí)驗(yàn)驗(yàn)證

本實(shí)驗(yàn)主要是在單臺(tái)計(jì)算機(jī)上，通過(guò)多個(gè)虛擬終端來(lái)仿真多臺(tái)計(jì)算機(jī)之間的通信過(guò)程，對(duì)比多數(shù)決和少數(shù)決選舉機(jī)制的選舉速度和安全性。采用C語(yǔ)言實(shí)現(xiàn)少數(shù)決選舉；通過(guò)修改的開(kāi)源libPaxos實(shí)現(xiàn)多數(shù)決選舉，并設(shè)所有服務(wù)器均承擔(dān)proposer和acceptor兩種角色；實(shí)驗(yàn)環(huán)境為Dell Precision移動(dòng)工作站，Intel Core i9-8950HK，2.9 GHz，32 GB DDR4內(nèi)存，操作系統(tǒng)為VMware Workstation虛擬機(jī)下的Ubuntu 16.4.04。

6.1 選舉成功率

模擬同一網(wǎng)段內(nèi)的8臺(tái)集群服務(wù)器。通過(guò)分別執(zhí)行1 000次多數(shù)決和少數(shù)決選舉，對(duì)比兩種選舉機(jī)制的規(guī)定時(shí)間內(nèi)選舉成功次數(shù)[18]。圖3展示了在250 ms、500 ms、1 000 ms內(nèi)，模擬集群服務(wù)器分別運(yùn)行多數(shù)決和少數(shù)決選舉機(jī)制，成功選舉出Leader的次數(shù)。

Fig.3 Comparison of the number of successful elections within specified time圖3 規(guī)定時(shí)間內(nèi)選舉成功次數(shù)對(duì)比

6.2 選舉安全性

模擬同一網(wǎng)段內(nèi)的8臺(tái)和10臺(tái)集群服務(wù)器兩種場(chǎng)景。通過(guò)執(zhí)行多數(shù)決和少數(shù)決選舉，對(duì)比兩種選舉機(jī)制的安全性。多數(shù)決時(shí)采用共同投票給P1的方式進(jìn)行攻擊，少數(shù)決時(shí)采用本文4.1節(jié)描述的：全力保證P1和盡可能多的隊(duì)友進(jìn)入下一輪的方式進(jìn)行攻擊。

圖4是在受控節(jié)點(diǎn)分別為1,2,…,8的情況下，分別采用經(jīng)典Paxos的多數(shù)決選舉機(jī)制和少數(shù)決選舉機(jī)制各進(jìn)行20次Leader選舉，統(tǒng)計(jì)擬定對(duì)象P1的獲勝次數(shù)。圖5是在受控節(jié)點(diǎn)分別為1,2,…,10的情況下分別采用經(jīng)典Paxos的多數(shù)決選舉機(jī)制和少數(shù)決選舉機(jī)制各進(jìn)行20次Leader選舉，統(tǒng)計(jì)擬定對(duì)象P1的獲勝次數(shù)。

Fig.4 Comparison of election security of 8 cluster servers圖4 8臺(tái)集群服務(wù)器選舉安全性對(duì)比

Fig.5 Comparison of election security of 10 cluster servers圖5 10臺(tái)集群服務(wù)器選舉安全性對(duì)比

6.3 實(shí)驗(yàn)結(jié)果分析

（1）多數(shù)決選舉機(jī)制和少數(shù)決選舉機(jī)制在成功選舉出Leader的所需時(shí)間基本一致。

（2）8臺(tái)集群服務(wù)器時(shí)分別使用兩種選舉機(jī)制發(fā)起絕對(duì)控制攻擊，少數(shù)決要比多數(shù)決多控制37.5%的節(jié)點(diǎn)才能確保攻擊成功，即少數(shù)決選舉安全性明顯高于多數(shù)決選舉。

（3）10臺(tái)集群服務(wù)器分別使用兩種選舉機(jī)制發(fā)起絕對(duì)控制攻擊，少數(shù)決要比多數(shù)決多控制30%的節(jié)點(diǎn)才能確保攻擊成功，即在表1中的低值時(shí)，少數(shù)決選舉安全性也遠(yuǎn)高于多數(shù)決選舉。

（4）對(duì)比圖4、圖5兩種選舉機(jī)制的斜率，少數(shù)決選舉只有在控制節(jié)點(diǎn)數(shù)臨近絕對(duì)控制攻擊滿足條件時(shí)，才會(huì)對(duì)獲勝次數(shù)產(chǎn)生明顯影響；而多數(shù)決選舉在隨控制節(jié)點(diǎn)數(shù)增加的初始階段，就對(duì)獲勝次數(shù)產(chǎn)生明顯的影響。

7 結(jié)束語(yǔ)

本文通過(guò)理論分析和實(shí)驗(yàn)證明，在分布式系統(tǒng)中采用少數(shù)決方式進(jìn)行Leader節(jié)點(diǎn)選舉是完全可行的，且少數(shù)決選舉機(jī)制相比多數(shù)決選舉機(jī)制在降低控票攻擊風(fēng)險(xiǎn)方面有明顯的優(yōu)勢(shì)。本文認(rèn)為此種選舉機(jī)制具有很好的科學(xué)性和進(jìn)一步的研究?jī)r(jià)值。下一步，將研究分析少數(shù)決選舉機(jī)制在其他領(lǐng)域的應(yīng)用潛力。