如何理解Kademlia节点操作的时间复杂度

Question

我正在通过阅读经典论文《Kademlia: A Peer-to-peer Information System Based on the XOR Metric》来学习Kademlia网络。我想了解它的操作复杂度，但仍无法理解。

在“3 Sketch of proof”部分中，论文给出了两个定义：

1. 节点深度（h）：160 - i，其中i是非空桶的最小索引
2. 节点y在节点x中的桶高度：x将y插入的桶的索引减去x的最不重要的空桶的索引。

以及三个结论：

1. 对于具有n个节点的系统，任何给定节点的高度都有很大的概率在常数的log n内。
2. 最接近ID的第k个节点的桶高度可能会在常数的log k内。
3. 如果这个节点的前h个最重要的k个桶都不为空，查找过程将在h - log k步内找到一半距离的节点（或者说其距离缩短了一位）。

所以我的问题是：

1. “最不重要的空桶”和“前h个最重要的k个桶”是什么意思？
2. 如何用直观的方式解释“节点深度”和“桶高度”？
3. 如何理解第二和第三个结论，即为什么是log k和h - log k？

- Justin Yang

Answer 1

我已经有一段时间没有真正阅读这篇论文了，所以我主要是通过我的实现经验来拼凑这个内容，而不是试图将我头脑中的概念与论文中的正式定义相匹配，因此请带着一点怀疑看待以下内容。

---

"最不重要的空桶"和"最重要的k桶"是什么意思？

这基本上是指相对于节点自身ID的XOR距离排序的桶。

如何用视觉方式解释深度和桶高度？

每个桶覆盖一个键空间区域。例如，从0x0000^{简化为2个字节}到0x0FFF表示1/16的键空间。这可以用类似CIDR的掩码表示，0x0/4（4个前缀位）。 这更或多或少是一个桶的深度。

有几种组织路由表的方法。“正确”的方法是将其表示为树形或基于桶所代表的最低ID的排序列表。 这种方法允许任意的桶分割操作，因为一些路由表优化需要，并且还可以用于实现节点多重归属。

一种简化的实现方式是使用固定长度的数组，并将每个桶放置在相对于节点自身ID的共享前缀位的位置。即，数组中的位置0将具有0个共享前缀位，它是最远的桶，覆盖50％的键空间和最重要的位是节点自身ID的反转MSB的桶。

在这种情况下，深度就是数组位置。

如何理解第二个和第三个结论，例如，为什么是log k和h-log k？

假设你正在寻找一个与你自己节点ID最远的ID。那么你只有一个桶覆盖该部分键空间，即它将用与你不同的最高有效位覆盖一半的键空间。因此，你会向来自该桶的一个（或多个）节点询问。由于他们的ID位与你的查找目标具有共同的第一位，他们几乎可以保证将其分成两个或更多个，即至少将目标空间的键空间覆盖范围加倍。因此，他们可以提供至少1位更好的信息。

当你查询接近目标的节点时，他们也会在目标区域附近具有更好的键空间覆盖范围，因为这也更接近他们自己的节点ID。

重复执行，直到找不到更近的节点为止。

由于每次跳跃至少切掉 1 比特的距离，所以你基本上需要 O(log(n)) 跳数，其中 n 是网络大小。由于网络大小基本上决定了节点之间的平均距离，从而需要你的主要桶的深度。

如果目标密钥靠近您自己的 ID，则需要较少的步骤，因为您将更好地覆盖该密钥空间区域。

由于 k 是一个常数（每个桶中的节点数），log k 也是一个常数。将桶中的节点数翻倍，它将具有给定键空间区域的两倍分辨率，因此（概率上）会产生比 k/2 大小的桶更接近目标的节点。也就是说，您必须将每个附加位每跳一次所需的条目数量翻倍。

---

编辑：这是一个实际的单宿主bittorrent DHT路由表的可视化，按其前缀排序，即与本地节点ID无关：

Node ID: 2A631C8E 7655EF7B C6E99D8A 3BF810E2 1428BFD4
buckets: 23 / entries: 173
000...   entries:8 replacements:8
00100...   entries:8 replacements:0
0010100...   entries:8 replacements:2
0010101000...   entries:8 replacements:4
00101010010...   entries:8 replacements:7
001010100110000...   entries:8 replacements:3
0010101001100010...   entries:8 replacements:3
00101010011000110000...   entries:8 replacements:1
001010100110001100010...   entries:3 replacements:0
0010101001100011000110...   entries:6 replacements:0
0010101001100011000111...   entries:6 replacements:0
0010101001100011001...   entries:8 replacements:2
001010100110001101...   entries:8 replacements:1
00101010011000111...   entries:8 replacements:2
00101010011001...   entries:7 replacements:0
0010101001101...   entries:8 replacements:0
001010100111...   entries:8 replacements:0
001010101...   entries:8 replacements:1
00101011...   entries:7 replacements:0
001011...   entries:8 replacements:0
0011...   entries:8 replacements:8
01...   entries:8 replacements:8
1...   entries:8 replacements:8

- the8472

---

非常感谢您的详细回答！然而，我仍然不明白第三个结论，也就是 h − log k 部分。为什么要减去 log k？ - Justin Yang

这是关键部分，其中密钥更接近您自己的ID而不是最远距离情况，我在第3个答案的最后一段中解释了这一点。请注意，k是桶的大小，log k因此与单个桶的“分辨率”有关。您必须使用指数级别更大的桶来保存每次跳跃的附加位。 - the8472

非常感谢，我现在可以理解log k了。还有一个问题：为什么是h“减去”log k，而不是“加上”呢？ - Justin Yang

因为更高的 k 值意味着每个桶中有更多的数据，从而减少了跳跃次数。 - the8472

Answer 2

这个被接受的答案很棒！

1. 我认为关于 h - logk 的解释可以简化。这是我对 h - logk 的理解。

从特定节点 u 的角度考虑问题。

对于您的 k 个最近邻居，您拥有完整的邻域信息。这是因为您将项目存储在大小为 k 的桶中，并且没有足够的键进入这些桶中，因此较低的叶子节点始终具有空的 k 桶。因此，您将知道所有 k 个最近的邻居。

现在，第 k 个最近的邻居在树中的高度是多少。 有 1 个键与其相差 1 位（最后一位不同） 有 2 个键与其相差 2 位（最后两位不同） 有 4 个键与其相差 3 位（最后三位不同） 因此，第 k 个最近的节点的高度 n 是

1 + 2 + 4 + ... + 2^n = k
=> 2^n = k + 1
=> n = log(k+1)

第k个远离节点的高度为log(k)。

这告诉我们，当您搜索距离<= logk（第k个节点的高度）的节点时，我们可以立即回答，因为我们知道完整的邻域，而且我们不需要花费logk步骤，在每个步骤中获取1位信息，就像在请求的节点更远时所需的那样。

因此，当我们搜索深度为h的节点时，最坏情况下会查询深度减少1的节点，直到找到一个节点，其深度为log k，并且该节点可以立即回答查询。

2.为了数学上回答您的第一个问题，具有压倒性概率的节点高度为O(log n)

考虑一个键为M位且网络中有N个节点的网络。现在，我们从特定节点u的角度来看路由树。由于一半的可能键位于顶部桶中，四分之一位于第二个桶中等等，因此该树将向高阶位拥挤。

So what is the probability that your first q slots
in the routing tree with distance 
from 2^0 - 2^1 to 2^q-1 - 2^q are empty.
This requires that all the N nodes fall in the buckets greater than q

To select a key in bucket greater than q you
need to ensure that your maximum prefix match is less than M-q.

So there are 2^M total keys of which 2^q keys 
have the same prefix of length (M-q) as the node u. 
So the favourable cases are 2^M - 2^q. 
Total cases are 2^M
Assume all N key draws are independent
So the probability that q lowest slots are empty is (1 - 1/2^(M-q))^N

So we plug in q = M - clog(n) which would mean 
that there are clog(n) filled buckets 
with M-clog(N) lower buckets empty

P = (1-1/2^(clog(N)))^N
  = (1-1/N^c)^N
this is approximately equal to 
1-1/N^(c-1)

随着c的增加，概率趋近于1，我们很可能只有clog(n)个顶部插槽填充在路由表中。

- sukunrt