protocols - 无限循环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. 由于手指表为空，节点本身返回到findSuccessor. 因此n'等于n。

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

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

score 6 · Accepted Answer

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

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

但似乎有一个更优雅的解决方案，更接近伪代码。当检查一个 ID 是否在区间内时（n，后继]（左排除，右包含），使检查循环。jDHTUQ 似乎这样做（从第 75 行开始。警告：非常丑陋的代码）：

恕我直言，以循环方式执行间隔检查似乎是正确的做法。您链接的论文说（第 4 页）：

符号 (a; b] 表示从（但不包括）a 顺时针移动直到到达（包括）b 所获得的 Chord 环段。

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

id is.in (n, n]

这应该会产生true，因为 id 位于紧随其后n并以 . 结尾的环内n。

1 回答 1