一種基于失效檢測器的快速異步系統(tǒng)共識(shí)算法

摘要：異步系統(tǒng)下的共識(shí)問題是容錯(cuò)方向中的關(guān)鍵問題。首先分析了幾種基于失效檢測器的共識(shí)算法，然后考慮減少響應(yīng)時(shí)間，對(duì)現(xiàn)有算法提出改進(jìn)。改進(jìn)后的算法滿足異步系統(tǒng)下共識(shí)問題的兩階段最低限度，并且在特定條件下可以在第一階段快速作出響應(yīng)。經(jīng)實(shí)驗(yàn)證明，改進(jìn)后的算法具有更快的響應(yīng)時(shí)間和較少的通信量。

關(guān)鍵詞：異步系統(tǒng)； 容錯(cuò)； 共識(shí)問題； 失效檢測器

中圖法分類號(hào)：TP302.8文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1001－3695(2007)01－0097－03

一致性問題是分布式計(jì)算中的常見問題。例如，在一個(gè)復(fù)制數(shù)據(jù)系統(tǒng)中，對(duì)復(fù)制數(shù)據(jù)進(jìn)行相同順序的操作；在復(fù)制傳感器系統(tǒng)中，對(duì)傳感器的值達(dá)成一致；在一個(gè)廣播系統(tǒng)中以相同的順序傳遞一個(gè)消息等。共識(shí)問題就是對(duì)一致性問題的本質(zhì)歸納。在消息傳遞系統(tǒng)中，任何復(fù)制容錯(cuò)系統(tǒng)都會(huì)涉及到共識(shí)問題，因此共識(shí)問題是容錯(cuò)研究中的一個(gè)關(guān)鍵問題。共識(shí)問題抽象地來說，就是要求一系列進(jìn)程對(duì)某個(gè)值(Value)達(dá)成一個(gè)共識(shí)。過程分為兩個(gè)原語，即Propose原語和Decide原語。Propose時(shí)每個(gè)進(jìn)程提出一個(gè)值v，Decide時(shí)所有正確進(jìn)程必須最終決定某個(gè)值。解決共識(shí)問題必須滿足以下條件：

（1）終止性，即所有正確進(jìn)程最終都要決定某個(gè)值。

（2）有效性，假如某個(gè)進(jìn)程決定了某個(gè)值，那么這個(gè)值必須是在Propose原語中由某個(gè)進(jìn)程所提出的。

（3）一致性，即所有進(jìn)程最終決定的必須是同一個(gè)值。

本文主要考慮異步系統(tǒng)下的共識(shí)問題，一個(gè)分布式系統(tǒng)如果是異步的，那么在消息延遲、時(shí)鐘漂移和執(zhí)行一步所消耗的時(shí)間上都沒有上限。共識(shí)問題看似簡單，但M. J. Fischer 等人[1]證明共識(shí)問題在異步系統(tǒng)模型中，只要出現(xiàn)一個(gè)崩潰進(jìn)程，那么共識(shí)問題就不能得到解決。原因主要在于進(jìn)程無法準(zhǔn)確得知一個(gè)很久沒有響應(yīng)的進(jìn)程究竟是崩潰了，還是只是運(yùn)行得比較緩慢。圍繞這個(gè)問題，研究者大概提出兩種主要途徑：①簡化問題的定義，如借助Random Oracles的方法；②允許各個(gè)分布式進(jìn)程有一段足夠的同步時(shí)間得到正確的結(jié)果，其中最主要的就是借助失效檢測器。失效檢測器的概念最早是由Chandra和Toueg[2]提出的，在文中給出了基于失效檢測器解決異步模型下共識(shí)問題的算法，基于失效檢測器的共識(shí)算法模型可以用圖1來表示。共識(shí)算法周期性地詢問失效檢測器，失效檢測器在被詢問時(shí)返回當(dāng)前所懷疑的錯(cuò)誤進(jìn)程，共識(shí)算法根據(jù)返回的結(jié)果來完成下一步運(yùn)算。所有的共識(shí)算法均具有縱容性，即只有當(dāng)失效檢測器的條件滿足時(shí)，共識(shí)算法才可能給出結(jié)果，并且給出的結(jié)果一定是正確的；當(dāng)失效檢測器的條件沒有滿足時(shí)，共識(shí)算法不會(huì)給出任何結(jié)果。

減少共識(shí)問題時(shí)間開銷的途徑有兩種：①采用提高失效檢測器的準(zhǔn)確度和靈敏度的方法，這方面已經(jīng)有很多研究；②從提高共識(shí)算法的效率方面考慮。近幾年來，有關(guān)基于失效檢測器的共識(shí)算法研究已經(jīng)有很多，如文獻(xiàn)[4，6，8]，從最早的四階段CT算法到兩階段的PR，MR算法，研究者提出了很多種基于失效檢測器的共識(shí)算法。本文分析了幾種典型的基于失效檢測器的共識(shí)算法，并在其基礎(chǔ)上作出改進(jìn)，改進(jìn)后的算法在穩(wěn)定狀態(tài)下兩階段可以完成共識(shí)，并且在特定的條件下，第一階段就可以快速給出結(jié)果，從而降低時(shí)間開銷。

1系統(tǒng)模型和定義

系統(tǒng)由一系列有限的n個(gè)進(jìn)程組成，n>1，進(jìn)程集合為∏={P1，…，Pn}，進(jìn)程可能發(fā)生崩潰性錯(cuò)誤（在這里我們不涉及到拜占庭性錯(cuò)誤），進(jìn)程發(fā)生崩潰以后不會(huì)自動(dòng)恢復(fù)。一個(gè)進(jìn)程在發(fā)生崩潰性錯(cuò)誤以前，我們把它稱為一個(gè)正確的進(jìn)程。發(fā)生崩潰性錯(cuò)誤的進(jìn)程數(shù)目f不能超過進(jìn)程總數(shù)n的一半(f

不可靠失效檢測器的概念最早是由Chandra 和 Toueg[2]提出的，每個(gè)進(jìn)程都連接一個(gè)本地的失效檢測器，負(fù)責(zé)對(duì)其他進(jìn)程進(jìn)行監(jiān)控，在被詢問時(shí)給出當(dāng)前所懷疑發(fā)生崩潰的進(jìn)程的集合。不可靠就是允許出現(xiàn)錯(cuò)誤的懷疑，如果發(fā)現(xiàn)將一個(gè)正確的進(jìn)程錯(cuò)誤地劃入到懷疑對(duì)象中，就將其從懷疑對(duì)象中移除。文中根據(jù)完整性和精確性兩種屬性將失效檢測器分類。其中◇S類失效檢測器被證明是在異步系統(tǒng)下完成共識(shí)算法的最低限度。

◇S類失效檢測器應(yīng)滿足：

（1）強(qiáng)完整性(Strong Completeness)，即最終每個(gè)崩潰進(jìn)程都被所有正確進(jìn)程懷疑。

（2）最終弱精確性(Eventual Weak Accuracy)，即存在一個(gè)時(shí)刻，當(dāng)過了這個(gè)時(shí)刻以后，至少存在一個(gè)正確的進(jìn)程不被其他所有正確進(jìn)程懷疑。

Ω類失效檢測器是另外一種典型的失效檢測器。Ω類失效檢測器被詢問時(shí)，所返回的結(jié)果是當(dāng)前唯一一個(gè)被認(rèn)為正確的進(jìn)程，即Leader進(jìn)程。在很長一段時(shí)間內(nèi)，可以同時(shí)存在幾個(gè)Leader進(jìn)程，但最終所有正確進(jìn)程應(yīng)該選擇同一個(gè)Leader進(jìn)程，即滿足條件：

最終決定權(quán)（Eventual Leadership），存在一個(gè)正確進(jìn)程P和一個(gè)時(shí)間t，在時(shí)間t后，任何正確進(jìn)程詢問失效檢測器的返回值均為進(jìn)程P。

2算法分析

2．1四階段CT共識(shí)算法

CT算法是由Chandra和Toueg[2]提出的，CT算法是一種輪轉(zhuǎn)協(xié)調(diào)者算法，如圖2所示。

每個(gè)進(jìn)程都有一個(gè)確定的編號(hào)，分別為p1，…，pn。為了完成一次共識(shí)，所有進(jìn)程都要執(zhí)行一定的輪數(shù)(Round)，每輪分為四個(gè)階段。執(zhí)行過程中各個(gè)進(jìn)程不一定都處在同一輪，每一輪中都會(huì)有唯一的一個(gè)協(xié)調(diào)者。協(xié)調(diào)者是輪轉(zhuǎn)的，第一輪，p1成為協(xié)調(diào)者；第二輪，p2成為協(xié)調(diào)者；以此類推，pi進(jìn)程在第kn+i輪時(shí)成為協(xié)調(diào)者。當(dāng)一個(gè)進(jìn)程成為協(xié)調(diào)者時(shí)，它試圖讓所有進(jìn)程對(duì)某個(gè)值達(dá)成共識(shí)，如果本輪協(xié)調(diào)者被大多數(shù)進(jìn)程所認(rèn)可，共識(shí)算法結(jié)束，問題解決；否則就進(jìn)入下一輪，由下一個(gè)協(xié)調(diào)者來完成同樣的工作。CT算法基于◇S類失效檢測器，要求崩潰進(jìn)程數(shù)目不能超過進(jìn)程總數(shù)的一半。

使用CT算法，在正常運(yùn)行情況下（沒有出現(xiàn)崩潰進(jìn)程，并且失效檢測器給出的結(jié)果是正確的）完成一次共識(shí)，每個(gè)進(jìn)程需要經(jīng)歷如圖2所示的四個(gè)階段。每次在共識(shí)算法開始時(shí)，算法都會(huì)默認(rèn)進(jìn)程P1為協(xié)調(diào)者，這在進(jìn)程P1沒有崩潰時(shí)不會(huì)對(duì)算法有任何影響，一旦進(jìn)程P1發(fā)生崩潰，勢必會(huì)延長共識(shí)算法完成的時(shí)間，而且決定權(quán)在協(xié)調(diào)者，如果協(xié)調(diào)者進(jìn)程運(yùn)行速度變慢，那么整個(gè)系統(tǒng)的時(shí)間開銷就會(huì)增加。

2．2兩階段共識(shí)算法

CT算法之后，研究者提出了幾種每輪兩階段的共識(shí)算法，如Fast Consensus[7]、MR算法[4]，這些算法在某些情況下可以經(jīng)兩階段完成一次共識(shí)，但都有一定的限制條件。P. Dutta 和R. Guerraoui[6]提出了一種新的基于Ω類失效檢測器的算法，這種算法在穩(wěn)定狀態(tài)下，進(jìn)程一輪經(jīng)歷兩個(gè)階段就可以完成一次共識(shí)，并且滿足Zero Degrading ，即在穩(wěn)定狀態(tài)下，完成一次共識(shí)需要的階段數(shù)相同，系統(tǒng)穩(wěn)定后，崩潰進(jìn)程不會(huì)增加共識(shí)算法的時(shí)間開銷。具體算法描述如下：

當(dāng)一個(gè)進(jìn)程Propose時(shí)，它同時(shí)開始運(yùn)行兩個(gè)任務(wù)。

任務(wù)1所有進(jìn)程都要執(zhí)行一定的輪數(shù)，每輪分為兩個(gè)階段，在這兩個(gè)階段各個(gè)進(jìn)程彼此交換一些信息，進(jìn)程Pi保存的信息有當(dāng)前失效檢測器認(rèn)為的正確進(jìn)程leaderi、估值estimatei（初始值為Pi提出值）、本輪號(hào)碼ri、中間值newestimatei（初始值為⊥）。

第一階段：進(jìn)程Pi發(fā)送leaderi和estimatei給其他所有進(jìn)程，并且等待進(jìn)程leaderi和

n+12-1

個(gè)進(jìn)程的消息。此時(shí)，

(1)如果在收到進(jìn)程leaderi的消息之前認(rèn)為進(jìn)程leaderi崩潰，或收到來自進(jìn)程Pj的消息，有l(wèi)eaderj≠leaderi那么newestimatei=⊥。

(2)如果收到進(jìn)程leaderi的消息，而且所有收到的其他進(jìn)程消息都認(rèn)為leaderi是正確進(jìn)程，那么newestimatei的值為進(jìn)程leaderi所提出的值v。

第二階段：進(jìn)程Pi再次發(fā)送newestimatei給所有其他進(jìn)程，并且等待

n+12

個(gè)進(jìn)程的消息。此時(shí)，

（1）如果收到的所有進(jìn)程消息的newestimate都為⊥，則進(jìn)入下一輪。

（2）如果收到的進(jìn)程消息有部分newestimate不為空，則把此值賦給estimatei，進(jìn)入下一輪。

（3）如果收到所有進(jìn)程消息的newestimate都為值v，則decide值為v，并且發(fā)送decide消息給其他所有進(jìn)程，完成一次共識(shí)。

任務(wù)2在接收到任何進(jìn)程的decide消息后，決定相同的值v，并且向其他進(jìn)程發(fā)送decide消息，完成一次共識(shí)。

這種算法在穩(wěn)定狀態(tài)下，進(jìn)程經(jīng)歷兩階段就可以完成一次共識(shí)。因?yàn)樵贑T算法中決定權(quán)只在于協(xié)調(diào)者，當(dāng)協(xié)調(diào)者運(yùn)行比較緩慢或者崩潰時(shí)會(huì)對(duì)整體運(yùn)行速度產(chǎn)生影響，而這種算法中每個(gè)進(jìn)程都可以自主地決定值，因此在完成相同工作量的情況下與CT算法相比，降低了時(shí)間開銷。

2．3快速共識(shí)算法

PR算法各個(gè)進(jìn)程在每個(gè)階段都需要向其他所有進(jìn)程發(fā)送消息，這樣通信量要大于其他算法。我們考慮利用算法的特性，使得算法能夠在某種特定條件下在第一階段就完成共識(shí)。首先分析文獻(xiàn)[3]中Ω類失效檢測器的實(shí)現(xiàn)方法，它采用的是Push模式，如圖3所示。被檢測進(jìn)程q周期性地發(fā)送Iamalive消息，以顯示其沒有發(fā)生崩潰。假如在時(shí)間T內(nèi)，p沒有收到q的消息，那么p認(rèn)為進(jìn)程q發(fā)生崩潰。初始時(shí)所有進(jìn)程相信進(jìn)程P1為唯一正確的進(jìn)程（P1為Leader），進(jìn)程P1開始發(fā)送Iamalive消息給P2，P3，…，Pn。通常，一個(gè)進(jìn)程Pi，只有當(dāng)trustedi=i，進(jìn)程Pi才會(huì)周期性地給后繼進(jìn)程Pi+1，…，Pn進(jìn)程發(fā)送Iamalive消息。假如trustedi≠i，那么進(jìn)程Pi所做的只是等待來自于進(jìn)程Ptrustedi的消息。在等待過程中如果在時(shí)間T內(nèi)沒有收到消息，則進(jìn)程Pi認(rèn)為進(jìn)程Ptrustedi崩潰，進(jìn)而相信進(jìn)程Ptrustedi+1為當(dāng)前的Leader進(jìn)程。在運(yùn)行過程中如果Pi收到了來自Pj的消息，并且j

圖3失效檢測器模型

目前已經(jīng)有文章證明兩階段是異步系統(tǒng)模型下完成共識(shí)問題的最低限度，但在一些特定條件下，共識(shí)問題可以在第一階段完成。我們?cè)趯?duì)PR算法進(jìn)行分析后，不難看出在第二階段只有Leader進(jìn)程所提出的值才可以成為最終的決定值，如果采用基于上述算法的Ω類失效檢測器，編號(hào)為Pi的進(jìn)程不可能認(rèn)為編號(hào)大于i的進(jìn)程為當(dāng)前的Leader，因此編號(hào)大于 n+12

的進(jìn)程在PR算法中無法得到大于進(jìn)程總數(shù)一半的進(jìn)程的認(rèn)同，也就無法成為Leader，所提出的值不可能成為最終的決定值。這樣就可以將所有進(jìn)程分為兩部分：①提議者(Proposer)進(jìn)程，即編號(hào)不大于 n+12 的進(jìn)程，它們所提出的值有可能會(huì)成為最終的決定值；②參與者(Participant)進(jìn)程，它們只是參與整個(gè)共識(shí)算法的運(yùn)行，而不能成為最終決定值的提議者。如果在第一階段中有一個(gè)提議者進(jìn)程在等待 n+12

個(gè)進(jìn)程消息過程中，收到了其他所有提議者進(jìn)程的消息，并且它們提出的值相同時(shí)，這個(gè)進(jìn)程就可以決定這個(gè)值，從而在第一階段完成共識(shí)。這種情況也是常見的，如在由一個(gè)三臺(tái)備份機(jī)組成的主動(dòng)復(fù)制容錯(cuò)系統(tǒng)中，要求對(duì)處理一個(gè)消息的前后次序進(jìn)行共識(shí)，在這種情況下，消息到達(dá)三臺(tái)備份機(jī)的次序在大多數(shù)情況下是相同的。同時(shí)考慮到崩潰情況的發(fā)生概率比較低，因此我們考慮一種快速達(dá)成共識(shí)的方法。在PR算法的第一階段中加入對(duì)消息來源的判斷，假如某個(gè)提議者進(jìn)程收到所有提議者進(jìn)程的消息，并且提出值相同，那么這個(gè)進(jìn)程就可以決定這個(gè)值，完成共識(shí)。下面是對(duì)算法的證明。有效性通過算法描述不難證明，下面證明終止性和一致性。

（1）終止性。因?yàn)橄到y(tǒng)要求崩潰進(jìn)程數(shù)目不能超過進(jìn)程總數(shù)的一半，所以提議者進(jìn)程中至少有一個(gè)進(jìn)程Pi是正確的，那么根據(jù)部分同步模型的定義，在經(jīng)過系統(tǒng)穩(wěn)定時(shí)間以后，Pi就成為其他所有正確進(jìn)程的Leader，并且最終得到大部分進(jìn)程的認(rèn)可，從而完成共識(shí)，達(dá)到終止性的要求。

（2）一致性。假如在算法的執(zhí)行過程中，某個(gè)進(jìn)程在第一階段決定了值v，這個(gè)進(jìn)程必然是提議者進(jìn)程，而且這時(shí)提議進(jìn)程值均為v，那么在此后的運(yùn)行過程中，如果有進(jìn)程決定某個(gè)值v′，那么v′必然等于值v，從而滿足一致性的要求，其余證明等同于PR算法的證明。

3試驗(yàn)和算法評(píng)估

在本節(jié)中，我們通過模擬實(shí)驗(yàn)來顯示在執(zhí)行相同工作量時(shí)PR算法和改進(jìn)后算法的性能對(duì)比。實(shí)驗(yàn)操作系統(tǒng)為Linux，實(shí)驗(yàn)平臺(tái)為NEKO[5]。在大多數(shù)時(shí)間下，進(jìn)程均處于正常運(yùn)行中，所以我們主要給出在沒有出現(xiàn)崩潰進(jìn)程的情況下的模擬試驗(yàn)結(jié)果。分別考慮了進(jìn)程總數(shù)n=3和n=5兩種情況下兩種算法的數(shù)據(jù)對(duì)比，實(shí)驗(yàn)的結(jié)果是通過NEKO時(shí)間觀察器來收集的。所有的進(jìn)程同時(shí)開始運(yùn)行，完成一次共識(shí)所需要的時(shí)間為最快完成共識(shí)的進(jìn)程所消耗的時(shí)間。測試的Consensus的類型為Binary Consensus，因此確保各個(gè)進(jìn)程提出的值有可能相同。改進(jìn)算法所得出的時(shí)間值為平均值，兩次共識(shí)之間有一定的時(shí)間間隔。表1和表2分別是PR算法和改進(jìn)后算法在進(jìn)程總數(shù)n=3和n=5的執(zhí)行時(shí)間。圖4為其執(zhí)行時(shí)間對(duì)比圖。

表1進(jìn)程總數(shù)n=3時(shí)兩種算法執(zhí)行時(shí)間

表2進(jìn)程總數(shù)n=5時(shí)兩種算法執(zhí)行時(shí)間

圖4PR算法和改進(jìn)后算法的執(zhí)行時(shí)間對(duì)比

4結(jié)束語

異步系統(tǒng)模型下的共識(shí)問題是容錯(cuò)方面的關(guān)鍵問題，基于失效檢測器的共識(shí)算法是解決共識(shí)問題的重要途徑。從最早的四階段CT算法到兩階段的MR算法和PR算法等，研究者提出了很多種方案。本文在PR算法的基礎(chǔ)上，結(jié)合一種Ω類失效檢測器的設(shè)計(jì)方法對(duì)算法提出改進(jìn)，改進(jìn)后的算法在特定情況下，可以在第一階段完成共識(shí)。經(jīng)實(shí)驗(yàn)證明，該算法具有更短的響應(yīng)時(shí)間和較少的通信量。

參考文獻(xiàn)：

［1］M J Fischer， N A Lynch， M D Paterson. Impossibility of Distributed Consensus with One Faulty Process[J]. Journal of ACM，1985，32(2):374382.

［2］T Chandra， S Toueg. Unreliable Failure Detectors for Reliable Distributed Systems[J]. Journal of ACM，1996，43(2):225267.

［3］M Larrea， A Fernandez， S Arevalo. Optimal Implementation of the Weakest Failure Detector for Solving Consensus[C].The 19th IEEE Symposium on Reliable Distributed Systems(SRDS)，2000.334.

［4］A Mostefaoui， M Raynal. Leaderbased Consensus[J].Parallel Processing Letters， 2001，11(1)：95107.

［5］P Urb’an， X D’efago， A Schiper. NEKO： A Single Environment to Simulate and Prototype Distributed Algorithms[C].Beppu City: Proceedings of the 15th International Conference on Information Networking (ICOIN)，IEEE Computer Society，2001.503511.

［6］P Dutta， R Guerraoui. Fast Indulgent Consensus with Zero Degradation[C]. Proceedings of the 4th European Dependable Computing Conference (EDCC)， 2002.191208.

［7］M Hurfin， M Raynal. A Simple and Fast Asynchronous Consensus Protocol Based on a Weak Failure Detector[J]. Distributed Computing， 1999，12(4)：209223.

［8］R Guerraoui， et al. Information Structure of Indulgent Consensus[J].IEEE Transactions on Computers，20-04，53(4)：453466.

作者簡介：

王剛(1980)，男，河南洛陽人，碩士研究生，主要研究方向?yàn)槿蒎e(cuò)計(jì)算；

張大方(1959)，男，教授，博導(dǎo)，博士，主要研究方向?yàn)檐浖蒎e(cuò)、網(wǎng)絡(luò)測試、軟件測試、可信系統(tǒng)與網(wǎng)絡(luò)；

楊金民(1967)，男，湖南寧鄉(xiāng)人，博士，主要研究方向?yàn)槿蒎e(cuò)計(jì)算、軟件容錯(cuò)。

注:本文中所涉及到的圖表、注解、公式等內(nèi)容請(qǐng)以PDF格式閱讀原文