protocols - 无限循环findSuccessor？

Question

我目前正在处理 Chord 协议(protocol)。

每个节点有两个函数，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 .由于finger表为空，节点本身返回 findSuccessor .因此 n'则等于 n .

之后， findSuccessor被调用 n' ，这是对自身的递归调用。

然后我们有一个无限循环......或者我错过了什么？

注意:伪代码取自 Chord: A Scalable Peer-to-peer Lookup Protocolfor Internet Applications ，第 5 页。

Answer 1

“jchord”的实现者似乎同意你的看法，因为他将以下代码添加到 findSuccessor :

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

但似乎有一个更优雅的解决方案，更接近伪代码。当检查一个 ID 是否在区间 (n, successor] (左边排除，右边包括) 时，使检查循环。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 页):

The notation (a; b] denotes the segment of the Chord ring obtained by moving clockwise from (but not including) a until reaching (and including) b.

如果是单个节点，您将检查是否

id is.in (n, n]

这应该产生 true因为 id 在 n 之后开始的环内并以 n 结尾.