1. 首页
  2. 问题
  3. 如何理解Kademlia节点操作的时间复杂度
小编典典

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

algorithm

我现在正在通过阅读经典论文Kademlia：基于XOR度量的对等信息系统来学习Kademlia网络。我想了解其操作的复杂性，但仍然无法弄清楚。

在 3证明草图 部分中，本文给出了两个定义：

  1. 节点深度（h） ：160 − i，其中i是非空桶的最小索引
  2. 节点y在节点x中的存储桶高度 ：x将插入y的存储桶的索引减去x的 最低有效空存储桶 的索引。

还有三个结论：

  1. 对于具有n个节点的系统，以给定的概率，任何给定节点的高度都将在 log n 的常数之内。
  2. 在第k个最接近的节点中，最接近ID的节点的存储区高度可能在 log k 的常数之内。
  3. 如果该节点的h个 最重要的k个桶 中没有一个为空，则查找过程将在每个步骤中找到一个接近一半的节点（或者距离更短一点），从而以 h-log k个 步骤打开该节点。

所以我的问题是：

  1. 什么是 “最低有效空桶” 和 “最高有效k桶” ？
  2. 如何以视觉方式解释 深度 和 铲斗高度 ？
  3. 如何理解第二个和第三个结论，例如，为什么 log k 和 h-log k ？

阅读 369

收藏
2020-07-28

共1个答案

小编典典

自从我真正阅读本文以来已经有一段时间了，所以我主要是从我的实施经验中将它们拼凑在一起，而不是尝试将我头脑中的概念与本文的正式定义相匹配，因此请采用再加一点盐

什么是“最低有效空桶”和“最高有效K桶”？

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

如何以视觉方式解释深度和铲斗高度？

每个存储桶覆盖一个键空间区域。例如，对于键空间的1/16，从0x0000 简化为2个字节到0x0FFF。这可以用类似于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
2020-07-28