如何理解Kademlia节点运行的时间复杂度
How to understand the time complexity of Kademlia node operation
我现在正在通过阅读经典论文来学习Kademlia网络Kademlia: A Peer-to-peer Information System Based on the XOR Metric。我想了解其操作的复杂性，但仍然无法弄清楚。
在3 Sketch of proof部分，论文给出了两个定义：
- 一个节点的深度(h): 160 − i，其中i是最小的索引
非空桶
- 节点 y 在节点 x 中的桶高度：x 将插入 y 的桶的索引减去 x 的最低有效空桶的索引.
以及三个结论：
- 对于具有 n 个节点的系统，任何给定节点的高度极有可能在 log n 的常数范围内。
- 距离第 k 个最近节点中的 ID 最近节点的桶高度可能在 log k.
的常数范围内
- 如果此节点的 h most significant k-buckets 的 none 为空，则查找过程将找到接近一半的节点（或者更确切地说，其距离为 1短一点）在每个步骤中，因此在 h − log k 步中打开节点。
所以我的问题是：
- 什么是"least significant empty bucket"和"most significant k-buckets"？
- 如何直观地解释深度和桶高？
- 如何理解第二个和第三个结论，比如说，为什么log k和h - log k?
自从我真正阅读这篇论文以来已经有一段时间了，所以我主要是根据我的实施经验将其拼凑在一起，而不是试图将我头脑中的概念与论文中的正式定义相匹配纸，所以对以下内容持保留态度
What is "least significant empty bucket" and "most significant k-buckets"?
基本上是指相对于节点自身ID按异或距离排序的桶
How to explain the depth and bucket height in visual way?
每个桶覆盖一个关键space区域。例如。从 0x0000 简化为 2 个字节 到 0x0FFF 1/16 的密钥 space。这可以用类似 CIDR 的掩码 0x0/4（4 个前缀位）表示。
这差不多是一个水桶的深度。
“正确”的方式是根据一个桶表示的最低ID将其表示为树或排序列表。
这种方法允许在某些路由 table 优化要求时进行任意存储桶拆分操作，并且还可以用于实现节点多宿主。
一个简化的实现可以改为使用固定长度的数组，并将每个桶放在相对于节点自身 ID 的共享前缀位的位置。 IE。数组中的位置 0 将具有 0 个共享前缀位，它是最远的桶，该桶覆盖 keyspace 的 50%，并且最高有效位是节点自身 ID 的反转 MSB 的桶。
在这种情况下，深度就是数组位置。
How to understand the second and third conclusions, say, why log k and h - log k?
假设您正在寻找与您自己的节点 ID 最远的 ID。那么你将只有一个桶覆盖 keyspace 的那部分，即它将覆盖 keyspace 的一半，最高有效位与你的不同。
因此，您从该存储桶中询问一个（或多个）节点。由于它们的 ID 位与您的查找目标有共同的第一位，它们或多或少可以保证将其分成两个或更多，即至少有两倍的 keyspace 覆盖目标 space.所以他们可以提供至少 1 位更好的信息。
当您查询更靠近目标的节点时，它们在目标区域附近也会有更好的键space 覆盖，因为这也更接近它们自己的节点 ID。
冲洗，重复直到找不到更近的节点。
由于每一跳一次至少减少 1 位距离，因此您基本上需要 O(log(n)) 跳数，其中 n 是网络大小。由于网络大小基本上决定了节点之间的平均距离，因此决定了你的主桶所需的桶深度。
如果目标密钥更接近您自己的 ID，您将需要更少的步骤，因为您将更好地覆盖该密钥区域space。
由于 k 是一个常量（每个桶的节点数）所以 log k 也是一个常量。将桶中的节点数量加倍，它将具有给定 keyspace 区域分辨率的两倍，因此将（概率上）产生一个比具有 [=49 的桶更接近目标的节点=] 大小。 IE。对于您希望保存的每个额外位，您必须将每个存储桶的条目数加倍。
编辑：这是实际单宿主 bittorrent DHT 路由的可视化 table，按前缀排序，即与本地节点 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
我现在正在通过阅读经典论文来学习Kademlia网络Kademlia: A Peer-to-peer Information System Based on the XOR Metric。我想了解其操作的复杂性，但仍然无法弄清楚。
在3 Sketch of proof部分，论文给出了两个定义：
- 一个节点的深度(h): 160 − i，其中i是最小的索引 非空桶
- 节点 y 在节点 x 中的桶高度：x 将插入 y 的桶的索引减去 x 的最低有效空桶的索引.
以及三个结论：
- 对于具有 n 个节点的系统，任何给定节点的高度极有可能在 log n 的常数范围内。
- 距离第 k 个最近节点中的 ID 最近节点的桶高度可能在 log k. 的常数范围内
- 如果此节点的 h most significant k-buckets 的 none 为空，则查找过程将找到接近一半的节点（或者更确切地说，其距离为 1短一点）在每个步骤中，因此在 h − log k 步中打开节点。
所以我的问题是：
- 什么是"least significant empty bucket"和"most significant k-buckets"？
- 如何直观地解释深度和桶高？
- 如何理解第二个和第三个结论，比如说，为什么log k和h - log k?
自从我真正阅读这篇论文以来已经有一段时间了，所以我主要是根据我的实施经验将其拼凑在一起，而不是试图将我头脑中的概念与论文中的正式定义相匹配纸，所以对以下内容持保留态度
What is "least significant empty bucket" and "most significant k-buckets"?
基本上是指相对于节点自身ID按异或距离排序的桶
How to explain the depth and bucket height in visual way?
每个桶覆盖一个关键space区域。例如。从 0x0000 简化为 2 个字节 到 0x0FFF 1/16 的密钥 space。这可以用类似 CIDR 的掩码 0x0/4（4 个前缀位）表示。 这差不多是一个水桶的深度。
一个简化的实现可以改为使用固定长度的数组，并将每个桶放在相对于节点自身 ID 的共享前缀位的位置。 IE。数组中的位置 0 将具有 0 个共享前缀位，它是最远的桶，该桶覆盖 keyspace 的 50%，并且最高有效位是节点自身 ID 的反转 MSB 的桶。
在这种情况下，深度就是数组位置。
How to understand the second and third conclusions, say, why log k and h - log k?
假设您正在寻找与您自己的节点 ID 最远的 ID。那么你将只有一个桶覆盖 keyspace 的那部分，即它将覆盖 keyspace 的一半，最高有效位与你的不同。 因此，您从该存储桶中询问一个（或多个）节点。由于它们的 ID 位与您的查找目标有共同的第一位，它们或多或少可以保证将其分成两个或更多，即至少有两倍的 keyspace 覆盖目标 space.所以他们可以提供至少 1 位更好的信息。
当您查询更靠近目标的节点时，它们在目标区域附近也会有更好的键space 覆盖，因为这也更接近它们自己的节点 ID。
冲洗，重复直到找不到更近的节点。
由于每一跳一次至少减少 1 位距离，因此您基本上需要 O(log(n)) 跳数，其中 n 是网络大小。由于网络大小基本上决定了节点之间的平均距离，因此决定了你的主桶所需的桶深度。
如果目标密钥更接近您自己的 ID，您将需要更少的步骤，因为您将更好地覆盖该密钥区域space。
由于 k 是一个常量（每个桶的节点数）所以 log k 也是一个常量。将桶中的节点数量加倍，它将具有给定 keyspace 区域分辨率的两倍，因此将（概率上）产生一个比具有 [=49 的桶更接近目标的节点=] 大小。 IE。对于您希望保存的每个额外位，您必须将每个存储桶的条目数加倍。
编辑：这是实际单宿主 bittorrent DHT 路由的可视化 table，按前缀排序，即与本地节点 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