基于貪心策略優化欺負算法

摘 要： 在分布式操作系統中，存在一個“協調者”的進程。當該進程發生停止工作后需要產生一個新的“協調者”，新的協調者的產生過程稱之為選舉過程，該過程的一個基本算法就是欺負算法，但是利用基本的欺負算法做選舉過程時需要進行大量的消息傳遞，這就可能會導致系統整體性能降低。這里對基本欺負算法進行仔細分析，并在分析參考了其他的一些相關優化措施的基礎上，我們提出了一種新的優化算法，它利用了貪心算法的策略對基本的欺負算法做了一定的優化，改善了系統的性能。

關鍵詞： 分布式算法 選舉算法 欺負算法 協調者 貪心算法

1.引言

隨著網絡軟件技術和硬件條件的發展，分布式技術如分布式操作系統、分布式數據庫技術等得以迅速發展，成為計算機科學與技術研究領域的一個熱點和重點。該技術越來越被廣泛應用，其中的算法問題也越來越受到重視。［１］

很多分布式算法需要有一個進程作為協調者、發起者或其他類似的角色。而如何選舉出這個特定協調者的算法，我們形象地稱之為選舉算法。選舉算法的目標是確保發起選舉后，當所有的進程都同意選出的新協調者時選舉結束。［２］本文主要是在研究基本欺負算法通信量大的缺陷后，對此問題上提出了一些優化措施，依靠減少通信量來達到系統的性能優化。

2.欺負算法及性能分析

2.1欺負算法

由Garcia-Molina（1982）提出，欺負算法總是找進程號最大的進程并把它指定為協調者，其基本思想是：當一個進程P發現協調者不再響應請求時，就判定協調者已經停止工作，于是它就發起選舉，選出當前活動進程中進程號最大的充當新的協調者。［３］

前提：假設當前有N個進程在運行，首先充當協調者的進程號是N。

（1）進程P（假設該進程的進程號是i）發送消息給協調者時發現沒有回應，則認定協調者已經停止工作，則進程P向其他進程號比它大的進程發送發起選舉的消息。

（2）如果沒有進程回應，則認為其他進程均已停止工作，當前進程P充當協調者。

（3）如果有其他進程響應，因為發送反饋消息的進程的進程號必定大于當前進程P，所以將選舉權交給響應者，響應者發起一輪新的選舉。

（4）響應者發起的選舉也要按照往大進程號發的規則進行，一直到找到進程號最大且正常運行的進程為止。此時一共發送的消息數為（N-i）+（N-i-1）+…+1個，接收到的反饋消息為（N-i-1）+（N-i-2）+…+1個。

（5）最后新的協調者將它獲勝的消息通知所有其他正常運行的進程。

2.2欺負算法舉例

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

2.3欺負算法分析

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

顯然，消息的數量和兩個問題有關，一個是第一個發現協調者停止工作的進程號，一個是總的進程數。第一個發現協調者停止工作的進程號越小，則選舉所要發送的消息數越多，總的進程數越大，所要發送的消息數也越多，而且前一個僅僅是一次函數關系，而后者是二次函數關系。所以我們需要對該算法進行一定的優化來減少消息數量的傳遞，以減輕網絡的負載問題和避免發生廣播風暴［４］問題。

3.算法優化

3.1優化思路

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

3.2優化后的算法過程

其基本思想是：

前提：假設運行的進程數為N，當前的協調者的進程號是最大值N。

（1）當一個進程P（假設該進程的進程號為i）發現協調者停止工作時就發起選舉，在發起選舉前，該進程首先搜索進程號列表，找出當前進程號最大的進程（崩潰的協調者除外，應該是N-1），然后向該進程發送選舉消息。這里就使用了貪心策略，直接找（看起來）最佳選擇。

（2）如果N-1號進程回發消息，則表示新的協調者產生，為N-1號進程，然后第N-1號進程向其他進程發送獲勝的消息，并承擔協調者的責任，此時發送的消息數一發一回兩條消息。

（3）如果第N-1號進程已經在這之前停止工作，則進程P將收不到回答消息，那它將繼續向第N-2號進程發送選舉消息，有反饋則該進程成為新的協調者，此時總的消息數是發送兩條，反饋一條，共三條消息。

（4）同樣的，如果還是沒有反饋，則一直回溯到第i+1號進程。此時已發的消息數為N-i-1，反饋消息為1條，共N-i條消息。

（5）如果第i+1號進程還是沒有反饋消息，則第i號進程，即進程P成為新的協調者。此時已發的消息數為N-i-1，沒有反饋消息，共N-i-1條消息。

3.3優化后的算法舉例

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

3.4優化后的算法分析

3.4.1優點

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

3.4.2缺點

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

所以該優化算法適用于網絡環境連接狀態良好（帶寬大小對該算法的影響不大），成員（即該系統中的獨立的計算機）的穩定程度高的的分布式系統。

4.結語

優化后的算法避免了不斷循環的選舉過程，在貪心得到滿足的情況下，最少只要經過一次信息交換就可以得出新的協調者，雖然這種優化還是有著它的缺陷，但是當分布式系統的健壯性逐步得到提高的時候，該算法的優越性也會越來越顯著，這種基于貪心策略的欺負算法改進還是很有效的。

參考文獻：

［1］馬寧，馬義忠.基于欺負算法的優化算法［J］.計算機工程，第34卷，（19）.

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

［3］陸麗娜.分布式操作系統［M］.北京：電子工業出版社，1999.

［4］禚連春.TCP/IP網絡廣播風暴控制技術［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.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文