Назначение свойств метрики XOR Kademlia

Я могу говорить только за Kademlia, может быть, кто-то другой может дать более общий ответ. В это время...

• d(x,x) = 0
• d(x,y) > 0, if x != y

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

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

• для всех x, y : d (x, y) = d (y, x)

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

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

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

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

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

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

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

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

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

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

Возьмем два узла с одинаковым расстоянием Хэмминга от «я» и длиной их префикса, общего с «я»: узел с кратчайшим общим префиксом является самым дальним узлом.

В документе используется «метрика расстояния XOR», но на самом деле она должна читаться как «общий порядок длины префикса идентификатора».

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

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