改变Kademlia度量-单向性质的重要性

Question

Kademlia使用XOR度量。除其他外，这被称为“单向”性质(=对于任意给定的点x和距离e>0，正好有一个点y，使得d(x，y)=e)。

第一个问题是一个普遍的问题:度量的这一属性对Kademlia的功能是至关重要的，还是仅仅是帮助揭示来自某些节点的压力(正如最初的论文所建议的)。换句话说，如果我们想改变度量，那么提供一个“单向”的度量又有多重要呢？

第二个问题是关于度量的具体变化:假设我们将节点标识符(地址)作为X位数，下面的任何一个度量都适用于Kademlia吗？

1. d(x,y) = abs(x-y)
2. d(x,y) = abs(x-y) + 1/(x xor y)

第一个度量只是提供数字之间的差异，因此对于节点ID 100，ID 90和110的节点是相等的，因此这不是单向度量。在第二种情况下，我们修正了添加1/( xor y)，其中我们知道( xor y)是单向的，所以拥有1/( xor y)应该保留这个属性。

因此，对于节点ID 100，节点ID 90是d(100,90) = 10 + 1/62，而从节点ID 110到节点ID 110的距离是d(100,110) = 10 + 1/10。

Answer 1

你就不会再和卡德米利亚打交道了。还有一些其他路由算法使用不同的距离度量，有些甚至是不统一的距离度量，但它们不依赖于特定于kademlia的假设，有时还会结合其他特性来弥补这些度量的一些不可取的方面。

由于度量中可以有联系(每个点有两个候选项)，所以查找不能再聚集在一组最接近的节点上。

桶分裂和其他路由表维护算法需要更改，因为它们假设相同的距离只能在节点标识下发生。

我不确定这是否会影响大O属性或卡迪玛利亚的其他担保。

不管怎样，这似乎是个X-Y问题。您希望修改度量以满足特定目标。也许您应该在设计时考虑到这个目标来选择路由覆盖。

d(x，y) =abs( xor )+1/(Xor y)

这似乎不切实际，整数除法受到四舍五入的影响。在现实中，您将不会处理如此小的数字，而是更大(例如160位)的数字，使除法也更加昂贵。