Eri*_*ick 16 distance xor kademlia
在Petar Maymounkov和DavidMazières 的Kademlia论文中,据说XOR距离是一个有效的非欧几里德度量,对于为什么有效度量的每个属性都是必要或有趣的解释有限,即:
为什么一个指标通常具有这些属性很重要？为什么在Kademlia Distributed Hash Table实现中路由查询的上下文中,每个属性都是必需的？
此外,本文提到,单向性(对于给定的x和距离L,仅存在单一的y表示,其d(X,Y)= 1)保证所有查询将沿着相同的路径收敛.为什么会这样？
Fra*_*ser 14
我只能代表Kademlia,也许其他人可以提供更一般的答案.同时...
- d(x,x)= 0
- d(x,y)> 0,如果x!= y
这两点一起有效地意味着最近点x是x本身; 每一个点都离得更远.(这看似直观,但XOR指标的其他方面则不然.)
在Kademlia的上下文中,这很重要,因为查找具有ID的节点x将使该节点成为最接近的节点.如果情况并非如此,那将是尴尬的,因为收敛的搜索x可能找不到节点x.
- forall x,y:d(x,y)= d(y,x)
Kademlia路由表的结构使得节点保持最接近它们的地址空间的详细知识,并且指数地减少对更远地址空间的了解.总之,一个节点试图保持所有的k它听到关于最近联系人.
对称性是有用的,因为它意味着这些最接近的接触中的每一个将保持对地址空间的类似部分的详细知识,而不是远程部分.
如果我们没有这个属性,那么将搜索看作更像是在钟面周围的一个方向上移动的时钟的手可能会有所帮助.1点钟(节点1)的节点在2点(30°)靠近节点2,但节点2远离节点1(330°).所以想象一下,我们正在寻找最接近3点的两个(即Node1和Node2).如果搜索到达Node2,它将不知道Node1,因为它距离很远.整个查找和拓扑必须改变.
- d(x,z)<= d(x,y)+ d(y,z)
如果不是这种情况,则节点在查找期间不可能知道其路由表中的哪些联系人返回.它会知道k最接近目标,但不能保证其他一个更远的接触不会产生更短的整体路径.
由于这种属性和单向性,从非常分离的点开始的不同搜索将倾向于沿着相同的路径收敛.
单向性意味着没有两个节点可以与给定点具有相同的距离.如果不是这种情况,那么目标点可以被距离它相同距离的一堆节点包围.然后各种不同的搜索将免费挑选任何通过.但是,单向性保证这一组中的一个最接近,并且在该组之间选择的任何搜索将始终选择相同的一个.
我一直在抨击这个问题很长一段时间:XOR - 如同不同位数,合适的汉明距离 - 怎么能成为总秩序的基础？
嗯,它不能,这样的度量本身对于可比较的关系是不够的,它所能做的就是围绕一个点转储节点.
然后我更仔细地阅读了这篇论文并注意到它说"XOR为整数值"并且它突然出现在我身上:症结不是"XOR度量",而是ID的公共前缀的长度(其中XOR是一种推导机制.)
从"self"获取具有相同Hamming距离的两个节点,并将其前缀的长度与"self"相同:具有最短公共前缀的节点是最远的节点.
本文使用"XOR距离度量"但它确实应该读作"ID前缀长度总排序"
我想这可以解释一下,请告诉我http://metaquestions.me/2014/08/01/shortest-distance-between-two-points-is-not-always-a-straight-line/
基本上每跳一次,如果它在一个完全填充的网络(极端)中一次只有一个比特,那么它将具有前一跳的两倍知识.当你融合时,知识就会更大,直到你到达最接近网络知识的最近节点.