無限循環findSuccessor？

對於每個節點有兩個功能，findSuccessor和closestPrecedingNode，其給定爲僞代碼。

findSuccessor是：

n.findSuccessor(id) 
    if(id is.in (n, successor]) 
    return successor; 
    else 
    n' = closestPrecedingNode(id); 
    return n'.findSuccessor(id);

closestPrecedingNode是：

n.closestPrecedingNode(id) 
    for i = m downto 1 
    if(finger[i] is.in (n, id)) 
     return finger[i]; 
    return n;

當創建一個節點，其後繼最初設置爲節點本身，並且其手指表是空的。現在

我的問題是，當只有一個節點發生了什麼，並且它要求除了它自己的ID任何 ID。然後findSuccessor運行else區塊並呼叫closestPrecedingNode。由於手指表是空的，節點本身返回到findSuccessor。因此n'然後等於n。

之後，在n'上調用findSuccessor，這是對其自身的遞歸調用。

然後我們有一個無限循環...或者我錯過了什麼？

注：僞代碼是從Chord: A Scalable Peer-to-peer Lookup Protocol for Internet Applications採取5頁

來源

2012-12-06 Golo Roden

的「jchord」的實施者似乎同意你的觀點，因爲他添加以下代碼findSuccessor：

if (this == successor) { 
    return this; 
}

但似乎更接近僞代碼更優雅的解決方案。當檢查一個ID是否在間隔（n，後繼）（左邊排除，右邊包括）時，使該檢查循環。jDHTUQ似乎這樣做（從第75行開始。警告：真的很醜陋的代碼）：

。

http://jdhtuq.svn.sourceforge.net/viewvc/jdhtuq/source_code/distributed_lookup_service/LookupService/src/co/edu/uniquindio/utils/hashing/Key.java?revision=63&view=markup

恕我直言，以循環的方式進行的時間間隔檢查似乎是做正確的事，你鏈接白皮書說（第4頁）：

的符號（A，b]表示通過從（但不包括）a順時針移動直到達到（並且包括）b而獲得的Chord環的段。

在單節點的情況下，你會檢查是否

id is.in (n, n]

應該產生true因爲ID是n之後立即開始，並與n結束環內。

來源

2012-12-10 17:07:36

就是這樣，很好:-)。所以它基本上歸結爲你定義爲「包含在區間內」的問題...... –

儘管如此，您提到的'this'和'successor'之間的比較是必要的，因爲手指表最初可能是空的，但是後繼可能已經被設置到另一個節點（例如直接加入之後）。然後'findSuccessor'的'if'可能會失敗，然後您需要進行比較以避免無限循環。 –

這個函數沒有機會進入無限循環，因爲如果DHT中只有一個節點（k），即節點k是它自己的後繼者，那麼包含它自己的任意任意ID將落入「順時針循環間隔」（ k，k]。 – amitkriit

無限循環findSuccessor？

回答

相關問題