无限循环findSuccessor？

Question

我目前正在处理Chord协议.

对于每个节点有两个功能,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:用于Internet应用程序的可扩展对等查找协议,第5页.

Answer 1

"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而获得的弦环的片段.

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

id is.in (n, n]

应该产生,true因为id在戒指开始之后n和之后开始n.