Kademlia的XOR度量指标属性及用途

22
在Petar Maymounkov和David Mazières的Kademlia论文中,它说XOR距离是一种有效的非欧几里得度量,但对于一个有效度量的每个属性为什么是必要或有趣的,解释都很有限,包括:
  • d(x,x) = 0
  • d(x,y) > 0,如果x!= y
  • 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),保证所有查询沿着相同的路径收敛。为什么会这样?
3个回答

15
我只能代表Kademlia说话,也许其他人可以提供更普遍的答案。同时...
这两点的结合实际上意味着最接近x的点是x本身;其他所有点都离x更远。(这可能看起来很直观,但XOR度量的其他方面并非如此。)
在Kademlia的背景下,这很重要,因为查找ID为x的节点将产生该节点作为最接近的结果。如果不是这种情况,那么收敛于x的搜索可能找不到节点x,这将会很尴尬。
Kademlia路由表的结构是使节点保持了对其最近的地址空间的详细知识,并以指数方式减少对更远地址空间的知识。简而言之,节点尝试保持所有它听到的k个最接近的联系人。
这种对称性很有用,因为它意味着每个最接近的联系人都将维护与其类似的地址空间部分的详细信息,而不是远程部分。
如果我们没有这个属性,可能有帮助将搜索想象成手表向一个方向移动的钟表的指针。1点钟处的节点(Node1)靠近2点钟处的Node2(30°),但Node2远离Node1(330°)。因此,想象一下我们正在寻找最接近3点钟的两个节点(即Node1和Node2)。如果搜索到达Node2,则它不会知道Node1,因为它离得很远。整个查找和拓扑结构都必须更改。
对于x、y、z三个点来说,x到z的距离小于等于x到y的距离加上y到z的距离。如果这不是这样的话,节点在查找期间将无法确定要返回其路由表中哪些联系人。它会知道距离目标最近的前k个联系人,但不能保证其他更远的联系人中没有一个可以提供更短的总路径。
由于这种特性和单向性,从非常远的点开始的不同搜索往往会汇聚到同一路径上。
单向性意味着没有两个节点可以从给定点拥有相同的距离。如果不是这样,那么目标点可能被一堆距离它相同的节点包围。那么各种不同的搜索可以随意选择其中任何一个通过。然而,单向性保证这堆节点中恰好有一个是最接近目标点的,并且任何选择在这组之间的搜索都将始终选择相同的节点。

7

我已经苦思冥想了很长时间:如何将异或运算——即不同位数的数量,即正确的海明距离——作为全序关系的基础?

嗯,它不能。这样一个度量标准本身并不足以建立可比较的关系,它只能把节点丢在某个点周围。

然后我仔细阅读了论文,发现它说的是“XOR作为整数值”,我恍然大悟:关键不在于“XOR度量标准”,而在于ID的公共前缀长度(其中XOR是一种派生机制)。

从“自身”到具有相同海明距离的两个节点,以及它们与“自身”拥有的公共前缀长度,请选择公共前缀最短的节点,该节点是最远的节点。

论文使用了“XOR距离度量标准”,但实际上应该称为“ID前缀长度总排序”。


那么它真的在寻找具有最大公共前缀的节点? - amirouche

6

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接