0

我正在看 Kademlia 的论文，我遇到了一个我无法理解的问题。

In a fully-populated binary tree of 160-bit IDs, the magnitude of the distance between two IDs is the height of the smallest subtree containing them both.

在此处输入图像描述

d(101,010) = 5 ^ 2 = 7
but Lowest Common Ancestor height is 4:Count from one or 3:Count from zero (root)

这个结果显然是错误的，我肯定有什么地方不对劲，那这句话应该怎么理解，期待你的回复。谢谢

Kademlia P2P 系统中的伪可靠广播

反过来，Kademlia 将其节点组织成二叉树。（有关 Kademlia 内部机制的深入讨论，请参阅 [2]。）节点之间的距离是使用 XOR（异或）函数计算的，它本质上捕捉了二叉树拓扑的思想。对于任何节点 A 和 B，它们的距离的大小 d(A,B)=AB，例如 d 的最重要的非零位是包含它们的最小子树的高度。

Kademlia：基于 XOR 度量的点对点信息系统

接下来我们注意到 XOR 捕获了隐含在我们基于二叉树的系统草图中的距离概念。在 160 位 ID 的完全填充的二叉树中，两个 ID 之间的距离大小是包含它们的最小子树的高度。当一棵树没有完全填充时，最接近 ID x 的叶子是其 ID 共享 x 的最长公共前缀的叶子。如果树中存在空分支，则可能存在多个具有最长公共前缀的叶子。在这种情况下，最接近 x 的叶将是通过翻转 x 中对应于树的空分支的位而产生的最接近 ID x~ 的叶。

4

1 回答 1

1

那句话是在谈论距离的大小，而不是确切的距离。确切的距离只是两个地址之间的 XOR。

在 101 和 010 的特定情况下，距离为 111，即最大可能距离，因此它们除了整个树本身之外不共享公共子树，因此幅度为 3 位（假设为 3 位密钥空间），这也是最大高度. CIDR 子网中的等价物是 /0 掩码，即 0 个共享前缀位。

于 2020-08-23T14:58:30.523 回答