Задачи оценки качества Kademlia XOR

Question

В Kademlia paper Петра Маймункова и Дэвида Мазьера говорится, что расстояние XOR является действительной неевклидовой метрикой с ограниченными объяснениями, почему каждое из свойств действительной метрики является необходимым или интересным , а именно:

• д (х, х) = 0
• д (х, у)> 0, если х = у
• FORALL х, у: д (х, у) = д (x, y) + d (y, z) - неравенство треугольника
0 (0)

Почему важно, чтобы метрика имела эти свойства в целом? Почему каждое из этих свойств необходимо в контексте запросов маршрутизации в реализации Kademlia Distributed Hash Table?

Кроме того, в документе упоминается, что однонаправленность (для заданного x и расстояния l существует только один y, для которого d (x, y) = l) гарантирует, что все запросы будут сходиться по одному и тому же пути , Почему это так?

Answer 1

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

• d (х, х) = 0
• d (х, у)> 0, если х! = У

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

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

• FORALL х, у: д (х, у) = д (у, х)

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

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

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

• д (х, г) < = д (х, у) + D (у, г)

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

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

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

Answer 2

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

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

Answer 3

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

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

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

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

В работе используется «исключающее расстояние метрики», но на самом деле следует читать «ID префикс длины полного порядка»