Я смотрел статью Кадемлии, и у меня возникла проблема, которую я не мог понять.
In a fully-populated binary tree of 160-bit IDs, the magnitude of the distance between two IDs is the height of the smallest subtree containing them both.
d(101,010) = 5 ^ 2 = 7
but Lowest Common Ancestor height is 4:Count from one or 3:Count from zero (root)
Этот результат явно неверен, и у меня должно быть что-то не так, поэтому как мне интерпретировать это предложение? Я с нетерпением жду вашего ответа. Спасибо
Псевдонадежное вещание в системе P2P Kademlia
Kademlia, в свою очередь, организует свои узлы в двоичное дерево. (Для более глубокого обсуждения внутренних механизмов Kademlia, пожалуйста, обратитесь к [2].) Расстояние между узлами рассчитывается с использованием функции XOR (исключающее ИЛИ), которая по существу отражает идею топологии двоичного дерева. Для любых узлов A и B величина расстояния до них d (A, B) = AB, например старший ненулевой бит d - это высота наименьшего поддерева, содержащего их обоих.
Kademlia: одноранговая информационная система, основанная на метрике XOR
Далее мы отметим, что XOR захватывает понятие расстояния, неявное в нашем скетче системы на основе двоичного дерева. В полностью заполненном двоичном дереве 160-битных идентификаторов величина расстояния между двумя идентификаторами равна высоте самого маленького поддерева, содержащего их оба. Когда дерево заполнено не полностью, ближайшим к идентификатору x листом является лист, идентификатор которого имеет самый длинный общий префикс x. Если в дереве есть пустые ветви, может быть более одного листа с самым длинным общим префиксом. В этом случае ближайший к x лист будет ближайшим к ID x˜ листом, полученным путем переворота битов в x, соответствующих пустым ветвям дерева.
