distance - Kademlia XOR度量标准属性用途

Question

在Petar Maymounkov和DavidMazières撰写的Kademlia paper中，有人说XOR距离是有效的非欧几里得度量，但对为何有效度量的每个属性为何必要或有趣的解释有限，即：


d（x，x）= 0
如果x！= y，则d（x，y）> 0
forall x，y：d（x，y）= d（y，x）-对称
d（x，z）<= d（x，y）+ d（y，z）-三角不等式


通常，对于度量而言，具有这些属性为何很重要？在Kademlia分布式哈希表实现中，为什么在路由查询的上下文中每个属性都是必需的？

此外，本文提到单向性（对于给定的x和距离l，仅存在一个y（d（x，y）= l））保证所有查询都将沿着同一路径收敛。为什么呢？

Answer 1

我只能代表Kademlia，也许其他人可以提供更一般的答案。同时...



d（x，x）= 0
如果x！= y，则d（x，y）> 0



这两个点有效地意味着最接近x的点是x本身。每隔一点就更远了。 （这看起来似乎很直观，但是XOR指标的其他方面却不是。）

在Kademlia的上下文中，这很重要，因为查找ID为x的节点将使该节点成为最接近的节点。如果不是这种情况，那将很尴尬，因为收敛到x的搜索可能找不到节点x。



全部x，y：d（x，y）= d（y，x）



Kademlia路由表的结构是这样的：节点维护着最接近它们的地址空间的详细知识，并以指数方式减少了对更远的地址空间的知识。简而言之，节点尝试保持其听到的所有k最近联系。

对称性很有用，因为它意味着这些最紧密的联系方式中的每一个都将保持对地址空间类似部分而不是远程部分的详细了解。

如果我们没有此属性，则将搜索视为更像是将时钟指针沿表盘的一个方向移动可能会有所帮助。 1点钟处的节点（Node1）在2点钟处（30°）靠近Node2，但是Node2远离Node1（330°）。因此，假设我们正在寻找最接近3点的两个位置（即Node1和Node2）。如果搜索到达Node2，则它不会知道Node1，因为它很远。整个查找和拓扑必须更改。



d（x，z）<= d（x，y）+ d（y，z）



如果不是这种情况，那么节点将不可能知道在查找期间要从其路由表中返回哪些联系人。它会知道最靠近目标的k，但不能保证其他较远的接触之一不会产生较短的总体路径。

由于具有这种特性和单向性，因此，从完全分开的点开始的不同搜索将趋于收敛于同一条路径。

单向性意味着到给定点的任何两个节点都不能具有相同的距离。如果不是这种情况，那么目标点可能会被一群距离目标点都相同距离的节点包围。然后，各种不同的搜索将可以自由选择任何要通过的搜索。但是，单向性保证了该组中的一个恰好是最接近的，并且在该组之间进行选择的任何搜索都将始终选择同一组。