面向超立方體的領導者選舉算法

Question

我遇到了一些問題，我必須爲面向超立方體設計領導者選舉算法。這應該通過使用輪次數等於超立方體的維度D的比賽來完成。在每個階段d中，相鄰d維超立方體的兩個候選領導者應該競爭成爲（d + 1）維超立方體的單個候選領導者，其是它們各自的超立方體的聯合。

Answer 1

以來，它一直我研究分佈式系統很長一段時間，但我希望這有助於一點:)

問題：Leader election與hypercube tolopogy的網絡。在這種拓撲中，每個節點都有D個鄰居（其中D是超立方體的維度）。由於超立方體是面向的，節點知道它們的哪些鏈接對應於每個維度。另外，我假設所有節點都標有一些唯一的ID，這是典型的這類問題。

如果我理解你的解決方案指南，算法看起來很簡單：一個節點恰好有D個狀態。在每個狀態下，它都沿着d軸與其鄰居進行通信。這種通信包括向其發送它所知道的最佳候選人的標識（當d = 1時，這僅僅是其自己的標識），並將其與對等體所接收的標識進行比較。現在節點知道它所屬的d階子立方體的最佳id（由座標軸1,2 ...，d定義）。這樣，在步驟D，所有節點都知道全局最好，並且該算法以達成共識完成。

例如，假定下面的拓撲結構（d = 2）和id的值：

(1) (2) 
    1-----2 
    |  | 
    |  | 
    4-----3 
    (4) (3) 

括號中的IDS表示到目前爲止由每個節點目前已知最好的ID。

第一次迭代（d = 1）沿水平軸的工作原理，並且終止如下：

(2) (2) 
    1-----2 
    |  | 
    |  | 
    4-----3 
    (4) (4) 

第二個（最後一個）迭代（d = 2）沿垂直軸的工作原理，並且終止如下所示：

(4) (4) 
    1-----2 
    |  | 
    |  | 
    4-----3 
    (4) (4) 

根據需要（最高ID）選擇了節點號4。

消息計數複雜

對於我們恰好具有2個消息（一個在每個方向）的超立方體的每個邊緣。由於維數爲D的超立方體中邊數的公式爲E = D * 2 ^（D-1），我們恰好有M = D * 2^D個消息。爲了計算作爲N（節點數）的函數的複雜度，回想一下N = 2^D，所以M = N * logN。