基于貪心策略優(yōu)化欺負(fù)算法

摘 要： 在分布式操作系統(tǒng)中，存在一個(gè)“協(xié)調(diào)者”的進(jìn)程。當(dāng)該進(jìn)程發(fā)生停止工作后需要產(chǎn)生一個(gè)新的“協(xié)調(diào)者”，新的協(xié)調(diào)者的產(chǎn)生過程稱之為選舉過程，該過程的一個(gè)基本算法就是欺負(fù)算法，但是利用基本的欺負(fù)算法做選舉過程時(shí)需要進(jìn)行大量的消息傳遞，這就可能會(huì)導(dǎo)致系統(tǒng)整體性能降低。這里對(duì)基本欺負(fù)算法進(jìn)行仔細(xì)分析，并在分析參考了其他的一些相關(guān)優(yōu)化措施的基礎(chǔ)上，我們提出了一種新的優(yōu)化算法，它利用了貪心算法的策略對(duì)基本的欺負(fù)算法做了一定的優(yōu)化，改善了系統(tǒng)的性能。

關(guān)鍵詞： 分布式算法 選舉算法 欺負(fù)算法 協(xié)調(diào)者 貪心算法

1.引言

隨著網(wǎng)絡(luò)軟件技術(shù)和硬件條件的發(fā)展，分布式技術(shù)如分布式操作系統(tǒng)、分布式數(shù)據(jù)庫技術(shù)等得以迅速發(fā)展，成為計(jì)算機(jī)科學(xué)與技術(shù)研究領(lǐng)域的一個(gè)熱點(diǎn)和重點(diǎn)。該技術(shù)越來越被廣泛應(yīng)用，其中的算法問題也越來越受到重視。［１］

很多分布式算法需要有一個(gè)進(jìn)程作為協(xié)調(diào)者、發(fā)起者或其他類似的角色。而如何選舉出這個(gè)特定協(xié)調(diào)者的算法，我們形象地稱之為選舉算法。選舉算法的目標(biāo)是確保發(fā)起選舉后，當(dāng)所有的進(jìn)程都同意選出的新協(xié)調(diào)者時(shí)選舉結(jié)束。［２］本文主要是在研究基本欺負(fù)算法通信量大的缺陷后，對(duì)此問題上提出了一些優(yōu)化措施，依靠減少通信量來達(dá)到系統(tǒng)的性能優(yōu)化。

2.欺負(fù)算法及性能分析

2.1欺負(fù)算法

由Garcia-Molina（1982）提出，欺負(fù)算法總是找進(jìn)程號(hào)最大的進(jìn)程并把它指定為協(xié)調(diào)者，其基本思想是：當(dāng)一個(gè)進(jìn)程P發(fā)現(xiàn)協(xié)調(diào)者不再響應(yīng)請(qǐng)求時(shí)，就判定協(xié)調(diào)者已經(jīng)停止工作，于是它就發(fā)起選舉，選出當(dāng)前活動(dòng)進(jìn)程中進(jìn)程號(hào)最大的充當(dāng)新的協(xié)調(diào)者。［３］

前提：假設(shè)當(dāng)前有N個(gè)進(jìn)程在運(yùn)行，首先充當(dāng)協(xié)調(diào)者的進(jìn)程號(hào)是N。

（1）進(jìn)程P（假設(shè)該進(jìn)程的進(jìn)程號(hào)是i）發(fā)送消息給協(xié)調(diào)者時(shí)發(fā)現(xiàn)沒有回應(yīng)，則認(rèn)定協(xié)調(diào)者已經(jīng)停止工作，則進(jìn)程P向其他進(jìn)程號(hào)比它大的進(jìn)程發(fā)送發(fā)起選舉的消息。

（2）如果沒有進(jìn)程回應(yīng)，則認(rèn)為其他進(jìn)程均已停止工作，當(dāng)前進(jìn)程P充當(dāng)協(xié)調(diào)者。

（3）如果有其他進(jìn)程響應(yīng)，因?yàn)榘l(fā)送反饋消息的進(jìn)程的進(jìn)程號(hào)必定大于當(dāng)前進(jìn)程P，所以將選舉權(quán)交給響應(yīng)者，響應(yīng)者發(fā)起一輪新的選舉。

（4）響應(yīng)者發(fā)起的選舉也要按照往大進(jìn)程號(hào)發(fā)的規(guī)則進(jìn)行，一直到找到進(jìn)程號(hào)最大且正常運(yùn)行的進(jìn)程為止。此時(shí)一共發(fā)送的消息數(shù)為（N-i）+（N-i-1）+…+1個(gè)，接收到的反饋消息為（N-i-1）+（N-i-2）+…+1個(gè)。

（5）最后新的協(xié)調(diào)者將它獲勝的消息通知所有其他正常運(yùn)行的進(jìn)程。

2.2欺負(fù)算法舉例

下面是欺負(fù)算法工作的例子，以6個(gè)進(jìn)程為例，進(jìn)程號(hào)分別為1到6號(hào)。開始時(shí)號(hào)碼最大的6號(hào)為協(xié)調(diào)者，如圖1（a）所示；但它突然停止工作，如果此時(shí)3號(hào)進(jìn)程首先發(fā)現(xiàn)并發(fā)起選舉，它向所有比它進(jìn)程號(hào)大的進(jìn)程4、5、6號(hào)發(fā)送選舉消息，如圖1（b）所示；進(jìn)程4、5號(hào)接收消息后發(fā)回OK消息，如圖1（c）所示；3號(hào)進(jìn)程收到第一個(gè)反饋消息時(shí)就表示自己的任務(wù)已經(jīng)完成，進(jìn)程號(hào)大的進(jìn)程已經(jīng)接管該選舉，此時(shí)4號(hào)進(jìn)程發(fā)起選舉，發(fā)送消息給5、6號(hào)，5號(hào)進(jìn)程發(fā)起選舉，發(fā)送消息給6號(hào)，如圖1（d）所示；則5號(hào)反饋消息給4號(hào)，而6號(hào)因?yàn)橐呀?jīng)發(fā)生停止工作，所以沒有反饋消息給5號(hào)，如圖1（e）所示；從而5號(hào)進(jìn)程成為新的協(xié)調(diào)者，并將該結(jié)果通知其他所有進(jìn)程，如圖1（f）所示。到此為止，選舉過程結(jié)束，系統(tǒng)恢復(fù)正常運(yùn)行。

2.3欺負(fù)算法分析

這樣我們可以得出總共的消息數(shù)（包括發(fā)送的和接收的）Message=［（N-i）+（N-i-1）+…+1］+［（N-i-1）+（N-i-2）+…+1］=N^2-2iN+i^2。那它的算法復(fù)雜度為O（n^2）。

顯然，消息的數(shù)量和兩個(gè)問題有關(guān)，一個(gè)是第一個(gè)發(fā)現(xiàn)協(xié)調(diào)者停止工作的進(jìn)程號(hào)，一個(gè)是總的進(jìn)程數(shù)。第一個(gè)發(fā)現(xiàn)協(xié)調(diào)者停止工作的進(jìn)程號(hào)越小，則選舉所要發(fā)送的消息數(shù)越多，總的進(jìn)程數(shù)越大，所要發(fā)送的消息數(shù)也越多，而且前一個(gè)僅僅是一次函數(shù)關(guān)系，而后者是二次函數(shù)關(guān)系。所以我們需要對(duì)該算法進(jìn)行一定的優(yōu)化來減少消息數(shù)量的傳遞，以減輕網(wǎng)絡(luò)的負(fù)載問題和避免發(fā)生廣播風(fēng)暴［４］問題。

3.算法優(yōu)化

3.1優(yōu)化思路

在前面第二部分中的選舉算法說明中，已經(jīng)提到我們假設(shè)每個(gè)進(jìn)程都知道所有其他進(jìn)程的進(jìn)程號(hào)，這就表示每個(gè)進(jìn)程中必定存在一張進(jìn)程號(hào)列表，但沒有記錄運(yùn)行狀態(tài)。下面我們利用這一特點(diǎn)，并利用貪心算法的原則：通過做一系列的選擇來給出某一問題的最優(yōu)解，對(duì)算法中的每個(gè)決策點(diǎn)，做一個(gè)當(dāng)時(shí)（看起來）最佳的選擇，雖然這種策略并不是總能產(chǎn)生出最優(yōu)解，［５］［６］來對(duì)基本欺負(fù)算法做一定的優(yōu)化。

3.2優(yōu)化后的算法過程

其基本思想是：

前提：假設(shè)運(yùn)行的進(jìn)程數(shù)為N，當(dāng)前的協(xié)調(diào)者的進(jìn)程號(hào)是最大值N。

（1）當(dāng)一個(gè)進(jìn)程P（假設(shè)該進(jìn)程的進(jìn)程號(hào)為i）發(fā)現(xiàn)協(xié)調(diào)者停止工作時(shí)就發(fā)起選舉，在發(fā)起選舉前，該進(jìn)程首先搜索進(jìn)程號(hào)列表，找出當(dāng)前進(jìn)程號(hào)最大的進(jìn)程（崩潰的協(xié)調(diào)者除外，應(yīng)該是N-1），然后向該進(jìn)程發(fā)送選舉消息。這里就使用了貪心策略，直接找（看起來）最佳選擇。

（2）如果N-1號(hào)進(jìn)程回發(fā)消息，則表示新的協(xié)調(diào)者產(chǎn)生，為N-1號(hào)進(jìn)程，然后第N-1號(hào)進(jìn)程向其他進(jìn)程發(fā)送獲勝的消息，并承擔(dān)協(xié)調(diào)者的責(zé)任，此時(shí)發(fā)送的消息數(shù)一發(fā)一回兩條消息。

（3）如果第N-1號(hào)進(jìn)程已經(jīng)在這之前停止工作，則進(jìn)程P將收不到回答消息，那它將繼續(xù)向第N-2號(hào)進(jìn)程發(fā)送選舉消息，有反饋則該進(jìn)程成為新的協(xié)調(diào)者，此時(shí)總的消息數(shù)是發(fā)送兩條，反饋一條，共三條消息。

（4）同樣的，如果還是沒有反饋，則一直回溯到第i+1號(hào)進(jìn)程。此時(shí)已發(fā)的消息數(shù)為N-i-1，反饋消息為1條，共N-i條消息。

（5）如果第i+1號(hào)進(jìn)程還是沒有反饋消息，則第i號(hào)進(jìn)程，即進(jìn)程P成為新的協(xié)調(diào)者。此時(shí)已發(fā)的消息數(shù)為N-i-1，沒有反饋消息，共N-i-1條消息。

3.3優(yōu)化后的算法舉例

下面是優(yōu)化后的算法工作的例子，同樣以6個(gè)進(jìn)程為例，進(jìn)程號(hào)分別從1到6號(hào)。開始時(shí)號(hào)碼最大的6號(hào)為協(xié)調(diào)者，如圖2（a）所示；但它突然發(fā)生停止工作，如果此時(shí)3號(hào)進(jìn)程首先發(fā)現(xiàn)并發(fā)起選舉，它向進(jìn)程號(hào)第二大的5號(hào)進(jìn)程發(fā)送選舉消息，如圖2（b）所示；進(jìn)程5號(hào)接收消息后發(fā)回OK消息，則此時(shí)5號(hào)進(jìn)程成為新的協(xié)調(diào)者，如圖2（c）所示；如果進(jìn)程5號(hào)也已經(jīng)停止工作，則3號(hào)進(jìn)程繼續(xù)向4號(hào)進(jìn)程發(fā)送選舉消息，如圖2（d）所示；4號(hào)進(jìn)程接收消息后發(fā)回OK消息，如圖2（e）所示；從而4號(hào)進(jìn)程成為新的協(xié)調(diào)者，并將該結(jié)果通知其他所有進(jìn)程，如圖2（f）所示。到此為止，選舉過程結(jié)束，系統(tǒng)恢復(fù)正常運(yùn)行。

3.4優(yōu)化后的算法分析

3.4.1優(yōu)點(diǎn)

從上面的工作過程我們可以得出總共的消息數(shù)（包括發(fā)送的和接收的）Message的值有很大的跳躍性，如果大進(jìn)程號(hào)的進(jìn)程沒有出現(xiàn)太多的故障，則消息數(shù)量都是單位數(shù)值，最壞的情況是第一個(gè)發(fā)現(xiàn)協(xié)調(diào)者故障的進(jìn)程以上的進(jìn)程都已經(jīng)故障，那么此時(shí)的消息數(shù)量是N-i-1。那它的算法復(fù)雜度為O（n）。

3.4.2缺點(diǎn)

我們可以發(fā)現(xiàn)，整個(gè)過程是基于貪心策略的，也就是說，我們的尋找方式只是從局部來考慮，而沒有從全局來考慮。如果第一次或者說前幾次找到的大進(jìn)程號(hào)進(jìn)程都已經(jīng)停止工作的話，那么我們需要等待越來越多的時(shí)間來讓進(jìn)程P找到合適的進(jìn)程充當(dāng)協(xié)調(diào)者，最差的情況就是一直找到i+1號(hào)進(jìn)程是已經(jīng)停止工作，最后只能由進(jìn)程P來充當(dāng)協(xié)調(diào)者，那么中間我們需要等待N-i次超時(shí)。這個(gè)時(shí)間的耗費(fèi)還是比較可觀的。

所以該優(yōu)化算法適用于網(wǎng)絡(luò)環(huán)境連接狀態(tài)良好（帶寬大小對(duì)該算法的影響不大），成員（即該系統(tǒng)中的獨(dú)立的計(jì)算機(jī)）的穩(wěn)定程度高的的分布式系統(tǒng)。

4.結(jié)語

優(yōu)化后的算法避免了不斷循環(huán)的選舉過程，在貪心得到滿足的情況下，最少只要經(jīng)過一次信息交換就可以得出新的協(xié)調(diào)者，雖然這種優(yōu)化還是有著它的缺陷，但是當(dāng)分布式系統(tǒng)的健壯性逐步得到提高的時(shí)候，該算法的優(yōu)越性也會(huì)越來越顯著，這種基于貪心策略的欺負(fù)算法改進(jìn)還是很有效的。

參考文獻(xiàn)：

［1］馬寧，馬義忠.基于欺負(fù)算法的優(yōu)化算法［J］.計(jì)算機(jī)工程，第34卷，（19）.

［2］Andrew S.Tanenbaum.Distributed Systems Principles and Paradigms［M］.Prentice Hall，2002.

［3］陸麗娜.分布式操作系統(tǒng)［M］.北京：電子工業(yè)出版社，1999.

［4］禚連春.TCP/IP網(wǎng)絡(luò)廣播風(fēng)暴控制技術(shù)［J］.Applications of the Computer Systems，2000.12.

［5］Cormen，Leiserson，and Rivest.Introduction to Algorithms［M］.The MIT Press，2001，Chapter 16“Greedy Algorithms”.

［6］http：//en.wikipedia.org/wiki/Greedy_algorithm.

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