Kademlia最小子树距离与高度的关系

Question

我在看卡德米利亚的论文，我遇到了一个我无法理解的问题。

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捕获了基于二叉树的系统草图中隐含的距离概念。在一个完全填充160位In的二叉树中，两个In之间距离的大小是包含这两个In的最小子树的高度。当树未完全填充时，与ID x最接近的叶子是ID共享最长的公共前缀x的叶子。如果树中有空分支，则可能有多个具有最长公共前缀的叶子。在这种情况下，离x最近的叶子将是与ID x˜最近的叶子，它是通过翻转与树的空分支对应的x中的位来产生的。

Answer 1

这句话指的是距离的大小，而不是确切的距离。确切的距离只是两个地址之间的XOR。

在101和010的特殊情况下，距离为111，这是最大的可能距离，因此，除了整个树本身之外，它们没有共享公共子树，因此大小为3位(假设3位键空间)，也是最大高度。在CIDR子网中等效的是/0掩码，即0共享前缀位。