Свойства метрики Kademlia XOR

Ответ 1

Я могу говорить только за Кадмелию, может быть, кто-то другой может дать более общий ответ. Тем временем...

• d (x, x) = 0
• d (x, y) > 0, если x!= y

Эти две точки вместе эффективно означают, что ближайшая точка к x сама x; все остальные точки дальше. (Это может показаться интуитивным, но другие аспекты XOR-метрики не являются.)

В контексте Kademlia это важно, так как поиск node с идентификатором x приведет к тому, что node будет самым близким. Было бы неудобно, если бы это было не так, поскольку поиск, сходящийся к x, может не найти node x.

• forall x, y: d (x, y) = d (y, x)

Структура таблицы маршрутизации Kademlia такова, что узлы поддерживают подробное знание ближайшего к ним адресного пространства и экспоненциально уменьшают знание более удаленного адресного пространства. Короче говоря, node пытается сохранить все k самые близкие контакты, о которых он слышит.

Симметрия полезна, поскольку она означает, что каждый из этих ближайших контактов будет поддерживать подробное знание аналогичной части адресного пространства, а не удаленной части.

Если бы у нас не было этого свойства, было бы полезно подумать о поиске, как о том, как руки часов движутся в одном направлении вокруг часовой пояс. node в 1 час (Node1) близок к Node2 в 2 часа (30 °), но Node2 далеко от Node1 (330 °). Итак, представьте, что мы ищем двух ближайших к 3 часам (т.е. Node1 и Node2). Если поиск достигнет Node2, он не будет знать об Node1, поскольку он далеко. Весь поиск и топология должны были бы измениться.

• d (x, z) <= d (x, y) + d (y, z)

Если бы это было не так, было бы невозможно, чтобы node знал, какие контакты из своей таблицы маршрутизации возвращаются во время поиска. Он знал бы, что k ближе всего к цели, но не будет никакой гарантии, что один из других более удаленных контактов не даст более короткий общий путь.

Из-за этого свойства и однонаправленности различные поиски, начиная с сильно разделенных точек, будут стремиться сходиться по тому же пути.

Однонаправленность означает, что ни один из двух узлов не может иметь одинаковое расстояние от данной точки. Если бы это было не так, то целевая точка могла быть окружена пучком узлов на всем расстоянии от него. Тогда различные различные поиски были бы бесплатными, чтобы выбрать любой из них, чтобы пройти. Однако однонаправленность гарантирует, что именно одна из этих групп будет самой близкой, и любой поиск, который выбирает между этой группой, всегда будет выбирать один и тот же.

Ответ 2

Я думаю, это может объяснить это немного, дайте мне знать http://metaquestions.me/2014/08/01/shortest-distance-between-two-points-is-not-always-a-straight-line/

В основном каждый прыжок, если он был только по одному бит за раз в полностью заполненной сети (экстремальный), имел бы в два раза больше информации о предыдущем прыжке. По мере того, как вы сходите, знание возрастает до тех пор, пока вы не дойдете до ближайших узлов, знания которых являются конечными в сети.

Ответ 3

Я довольно долго бил головой об этом: как может XOR - как в числе разных бит, правильное расстояние Хэмминга - быть основой общего порядка?

Ну, этого не может быть, такой метрики само по себе недостаточно для сопоставимого отношения, все, что он может сделать, - это дамп-узлы в кругах вокруг точки.

Затем я более внимательно прочитал документ и заметил, что он говорит "XOR как целочисленное значение", и это меня осенило: суть не "метка XOR", а длина общего префикса идентификатора ( из которых XOR является механизмом деривации.)

Возьмите два узла с тем же расстоянием Хэмминга от "Я" и длину их префикса, общий для "я": один с самым коротким общим префиксом является самым дальним node.

В документе используется "метрика расстояния XOR", но она действительно должна читать "полное задание длины префикса идентификатора"