許多分散式演算法需要某個行程擔任協調者（coordinator）、發起者（initiator）或其他特殊角色。一般而言由哪個行程擔任並不重要，但總得有一個來當。本節討論選出協調者（作為特殊行程的通稱）的演算法。

若所有行程一模一樣、毫無可資區別的特徵，就無從挑出特殊的那一個。因此我們假設每個行程有唯一編號，例如網路位址（為簡化，假設一台機器一個行程）。選舉演算法通常試圖找出編號最高的行程指定為協調者，差別只在於怎麼找。

此外假設每個行程都知道其他所有行程的編號；行程不知道的是哪些行程目前活著、哪些掛了。選舉演算法的目標：選舉開始後，最終所有行程都同意新協調者是誰。重要的演算法與變形可見 Lynch (1996) 與 Tel (2000) 的教科書。

傳統選舉演算法#

先看兩個傳統演算法，一窺過去數十年整群研究者在做什麼；後面兩小節再看選舉問題的新應用。

霸凌演算法#

第一個例子是 Garcia-Molina (1982) 提出的霸凌演算法（bully algorithm）。任何行程發現協調者不再回應請求時，就發起選舉。行程 P 這樣進行選舉：

1. P 送 ELECTION 訊息給所有編號比它高的行程。
2. 若無人回應，P 勝選成為協調者。
3. 若有編號較高者回應，由對方接手，P 的工作結束。

任何時刻，行程都可能收到編號較低的同僚送來的 ELECTION 訊息。此時接收者回覆 OK，表示自己還活著、會接手，然後（若還沒在辦）自己發起一場選舉。最終除了一個行程之外全都放棄，那個行程就是新協調者，並向所有行程宣布勝選：從現在起它是新協調者。

先前掛掉的行程恢復後會發起一場選舉。若它恰好是當前運行中編號最高的行程，就會勝選接下協調者的工作——鎮上最大塊頭的永遠贏，「霸凌演算法」因此得名。

範例走一遍：八個行程的霸凌選舉

群組有編號 0 到 7 的八個行程。原協調者行程 7 剛當機，行程 4 最先發現：

• 4 送 ELECTION 給比它高的 5、6、7。
• 5 和 6 都回 OK。4 收到第一個回應就知道自己的工作結束了——這些大人物之一會接手成為協調者，它坐等結果（雖然這時已能猜個八九不離十）。
• 5 和 6 各自舉行選舉，同樣只送訊息給比自己高的行程。
• 6 回覆 5，告訴它別再選了。此時 6 知道 7 死了，勝者是自己。若有狀態資訊要從磁碟或別處收集以銜接舊協調者的工作，6 此時處理。
• 準備好後，6 向所有運行中的行程送 COORDINATOR 訊息宣布接手。4 收到後，就能以 6 為協調者，繼續當初發現 7 死掉時正要做的操作。

7 的故障就此處理完畢，工作得以繼續。若行程 7 之後重新啟動，它只需向其他所有行程送 COORDINATOR 訊息，把大家霸凌到服從。

環演算法#

另一個選舉演算法基於環，但與某些環演算法不同，不使用權杖。假設行程們有實體或邏輯順序，每個行程知道自己的後繼者是誰。

• 任一行程發現協調者失靈時，建立一則含自己行程編號的 ELECTION 訊息，送給後繼者；後繼者掛了就跳過去找下一個、再下一個，直到找到活著的行程。
• 訊息沿途每經過一站，發送者把自己的編號加入訊息中的清單，等於把自己列為協調者候選人。
• 訊息最終繞回發起者——發起者收到含有自己編號的訊息時便認出這件事。此時訊息型別改為 COORDINATOR 再繞一圈，通知所有人：協調者是誰（清單中編號最高的成員）、以及新環的成員有哪些。這圈繞完，訊息即被移除，大家回去工作。

若兩個行程（例如 2 和 5）同時發現原協調者行程 7 當機，各自建立 ELECTION 訊息、各自開始繞環？沒關係：兩則訊息都會繞完全程，2 和 5 都會把它們轉成 COORDINATOR 訊息，而且成員與順序完全相同；再繞一圈後兩則都被移除。多幾則訊息繞行無傷大雅，頂多耗一點頻寬，不算浪費。

無線環境中的選舉#

傳統選舉演算法的假設在無線環境中通常不切實際：它們假設訊息傳遞可靠、網路拓撲不變。這些假設在多數無線環境——尤其是行動隨意網路（mobile ad hoc network）——都不成立。

能在隨意網路中運作的選舉協定不多。Vasudevan et al. (2004) 提出的解法能處理節點故障與網路分割，其重要特性是能選出「最佳」的領導者，而非像前面的解法那樣多少是隨機的一個。為簡化討論，這裡只考慮隨意網路、忽略節點會移動。

協定運作如下：

• 網路中任一節點（稱為來源，source）都可發起選舉：向其直接鄰居（範圍內的節點）送 ELECTION 訊息。節點第一次收到 ELECTION 時，把發送者指定為自己的父節點（parent），然後向父節點以外的所有直接鄰居轉送 ELECTION。收到來自「非父節點」的 ELECTION 時，只回一個確認。
• 節點 R 指定 Q 為父節點後，會先把 ELECTION 轉給（Q 以外的）直接鄰居、等收齊它們的確認，才回覆 Q 的 ELECTION。這個等待有重要後果：已經有父節點的鄰居會立即回應 R；若所有鄰居都已有父節點，R 是葉節點，可以很快回報 Q。回報時，R 同時附上自己的電池壽命與其他資源容量等資訊。
• 這些資訊讓 Q 得以比較 R 與其他下游節點的能力，選出最有資格擔任領導者的節點。Q 當初也是因為自己的父節點 P 送來 ELECTION 才轉發的；當 Q 最終回覆 P 時，同樣把最有資格的節點往上報。如此，來源最終會知道哪個節點最適合當領導者，再把結果廣播給所有其他節點。

範例走一遍：以容量選領導者

節點標為 a 到 j，各自帶著容量值。節點 a 發起選舉，向 b 與 j 廣播 ELECTION；訊息逐步傳遍所有節點，形成一棵以 a 為根的樹（建樹階段）。之後每個節點把「已知容量最佳的節點」回報給父節點：例如節點 g 收到子節點 e 與 h 的確認後，發現 h 最佳，就把 [h, 8] 往上傳給自己的父節點 b。最終來源 a 得知 h 是最佳領導者，並將此資訊廣播給所有節點。

多場選舉同時發起時，每個節點只加入一場：每個來源為自己的 ELECTION 訊息蓋上唯一識別碼，節點只參加識別碼最高的那場選舉，並停止其他選舉的參與。經過一些小調整，此協定也能在網路分割、節點加入與離開時運作，細節見 Vasudevan et al. (2004)。

大規模系統中的選舉#

前述演算法通常適用於相對小型的分散式系統，且只選一個節點。有些情境需要選出多個節點——例如第 2 章談過的 P2P 網路中的超級節點（superpeer）。本小節專注於超級節點的選擇問題。Lo et al. (2005) 指出超級節點的選擇需滿足下列要求：

1. 一般節點應能以低延遲存取超級節點。
2. 超級節點應均勻分布於覆蓋網路。
3. 超級節點占全網節點的比例應是預先定義的。
4. 每個超級節點服務的一般節點數不應超過固定上限。

所幸在多數 P2P 系統中這些要求相對容易達成，因為覆蓋網路要嘛是結構化的（DHT 系統）、要嘛是隨機非結構化的（例如以流言式協定實現）。以下看 Lo 等人提出的兩種解法。

DHT 系統：保留識別碼空間#

基本想法是保留一部分識別碼空間給超級節點。DHT 系統中每個節點獲得隨機且均勻分配的 m 位元識別碼；假設保留最前（最左）k 個位元來識別超級節點——需要 N 個超級節點時，取 k 為 log₂(N) 的上取整。

以 m = 8、k = 3 的小型 Chord 系統為例：查找負責鍵 p 的節點時，可以先把查找請求繞送給負責下列位元模式的節點，把它當作超級節點：

p AND 11100000

每個節點也能用同樣的查找檢查自己是否為超級節點（看請求是否繞回自己）。只要節點識別碼均勻分配，全網共 N 個節點時，超級節點的平均數量就是 2^(k−m) · N。

幾何空間：權杖與斥力#

完全不同的另一種做法，建立在前一節「把節點定位於 m 維幾何空間」之上。假設要把 N 個超級節點均勻散布在覆蓋網路中，基本想法很簡單：

• 把 N 個權杖散給 N 個隨機挑選的節點，任何節點不得持有多於一個權杖。
• 每個權杖代表一股斥力（repelling force），使其他權杖傾向遠離。若所有權杖的斥力相同，它們會彼此推開，在幾何空間中均勻散開。
• 持有權杖的節點必須得知其他權杖的存在：Lo 等人用流言式（gossiping）協定把權杖的力散播到全網。節點若發現作用在自己身上的合力超過門檻，就把權杖朝合力的方向移動。
• 權杖在同一節點停留達一定時間後，該節點就把自己升格為超級節點。