Как понять временную сложность работы узла Kademlia
Сейчас я изучаю сеть Kademlia, читая классическую статью " Kademlia: одноранговая информационная система на основе метрики XOR". Я хочу понять сложность его работы, но все еще не могу понять это.
В разделе " 3 эскиза доказательства " статья дает два определения:
- Глубина узла (h): 160 - i, где i - наименьший индекс непустого сегмента
- Высота сегмента y узла y в узле x: индекс сегмента, в который x будет вставлять y, минус индекс наименее значимого пустого сегмента x.
И три вывода:
- С подавляющей вероятностью высота любого данного узла будет в пределах константы log n для системы с n узлами.
- Высота сегмента ближайшего узла к идентификатору в k-м ближайшем узле, вероятно, будет в пределах константы log k.
- Если ни одно из h- значимых k-сегментов этого узла не является пустым, процедура поиска будет находить узел на половине ближе (или, точнее, расстояние которого на один бит короче) на каждом шаге и, таким образом, поворачивать узел за h - log k шагов,
Итак, мои вопросы:
- Что такое "наименее значимое пустое ведро" и "наиболее значимое k-ведро"?
- Как объяснить глубину и высоту ковша визуально?
- Как понять второй и третий выводы, скажем, почему log k, а h - log k?
2 ответа
Прошло много времени с тех пор, как я на самом деле прочитал статью, поэтому я в основном собираю это воедино из своего опыта реализации вместо того, чтобы пытаться сопоставить концепции, которые у меня в голове, с формальными определениями в статье, поэтому возьмите следуя с небольшим количеством соли
Что такое "наименее значимое пустое ведро" и "наиболее значимое k-ведро"?
Это в основном относится к сегментам, отсортированным по расстоянию XOR относительно собственного идентификатора узла.
Как объяснить глубину и высоту ковша визуально?
Каждое ведро охватывает область клавиш. Например, с 0x0000,упрощенного до 2 байтов, до 0x0FFF для 1/16 части пространства ключей. Это может быть выражено в CIDR-подобных масках, 0x0/4 (4 префиксных бита). Это более или менее глубина ведра.
Есть несколько способов организовать таблицу маршрутизации. "Правильный" способ - представить его в виде дерева или отсортированного списка на основе самого низкого идентификатора, представленного сегментом. Этот подход допускает произвольные операции разбиения по сегментам, как это требуется для некоторых оптимизаций таблицы маршрутизации, и может также использоваться для реализации множественного поиска узлов.
Упрощенная реализация может вместо этого использовать массив фиксированной длины и помещать каждый сегмент в положение битов общего префикса относительно собственного идентификатора узла. Т.е. позиция 0 в массиве будет иметь 0 общих префиксных битов, это самый дальний сегмент, сегмент, занимающий 50% пространства ключей, и сегмент, где наиболее значимым битом является инвертированный MSB собственного идентификатора узла.
В этом случае глубина - это просто позиция массива.
Как понять второй и третий выводы, скажем, почему log k, а h - log k?
Скажем, вы ищете идентификатор, который находится дальше всего от идентификатора вашего собственного узла. Тогда у вас будет только одна корзина, покрывающая эту часть пространства клавиш, а именно она покроет половину пространства клавиш с наиболее значимым битом, отличающимся от вашего. Таким образом, вы запрашиваете один (или несколько) узлов из этого сегмента. Благодаря тому, что их биты идентификатора имеют первый общий бит с целевой целью поиска, они более или менее гарантированно разделят их на две или более, то есть, по крайней мере, удвоят покрытие пространства ключей для целевого пространства. Таким образом, они могут предоставить по крайней мере 1 бит лучше информации.
По мере того, как вы будете запрашивать более близкие узлы к цели, они также будут иметь лучшее покрытие пространства ключей вблизи целевой области, поскольку это также ближе к их собственному идентификатору узла.
Промыть, повторять до тех пор, пока не будет найдено более близких узлов.
Так как каждый прыжок сбрасывает как минимум 1 бит расстояния за раз, вам, в основном, нужно количество переходов O(log(n)), где n - размер сети. Так как размер сети в основном определяет среднее расстояние между узлами и, следовательно, глубину корзины, необходимую для вашего домашнего сегмента.
Если целевой ключ ближе к вашему собственному идентификатору, вам потребуется меньше шагов, так как у вас будет лучший охват этой области пространства клавиш.
Так как k является константой (число узлов на ведро), то и log k. Удвойте количество узлов в сегменте, и у него будет удвоенное разрешение в данной области пространства ключей, и, таким образом (вероятностно), вы получите узел, который на один бит ближе к цели, чем сегмент с размером k/2. Т.е. вам нужно удваивать количество записей на группу для каждого дополнительного бита на каждый прыжок, который вы хотите сохранить.
Изменить: Вот визуализация фактической таблицы маршрутизации DHT с одним домом, отсортированной по префиксам, то есть не относительно идентификатора локального узла:
Node ID: 2A631C8E 7655EF7B C6E99D8A 3BF810E2 1428BFD4
buckets: 23 / entries: 173
000... entries:8 replacements:8
00100... entries:8 replacements:0
0010100... entries:8 replacements:2
0010101000... entries:8 replacements:4
00101010010... entries:8 replacements:7
001010100110000... entries:8 replacements:3
0010101001100010... entries:8 replacements:3
00101010011000110000... entries:8 replacements:1
001010100110001100010... entries:3 replacements:0
0010101001100011000110... entries:6 replacements:0
0010101001100011000111... entries:6 replacements:0
0010101001100011001... entries:8 replacements:2
001010100110001101... entries:8 replacements:1
00101010011000111... entries:8 replacements:2
00101010011001... entries:7 replacements:0
0010101001101... entries:8 replacements:0
001010100111... entries:8 replacements:0
001010101... entries:8 replacements:1
00101011... entries:7 replacements:0
001011... entries:8 replacements:0
0011... entries:8 replacements:8
01... entries:8 replacements:8
1... entries:8 replacements:8
Принятый ответ великолепен!
- Я думаю, что объяснение, связанное с h - logk, можно упростить. Вот как я думаю о h - log k.
Рассмотрите вещи с точки зрения конкретного узла u.
Для ваших k ближайших узлов у вас есть полная информация о окрестности. Это связано с тем, что вы храните элементы в корзинах размера k, и не хватает ключей для входа в эти корзины, поэтому, по сути, нижние листья всегда будут иметь пустые k корзин. Таким образом, вы будете знать всех своих k ближайших соседей.
Теперь, как высоко находится k-й ближайший сосед в дереве. есть 1 ключ на расстоянии 1 бит (последний бит отличается) есть 2 ключа на расстоянии 2 бита (последние два бита отличаются) есть 4 ключа на расстоянии 3 бита (последние 3 бита отличаются), поэтому высота n k-го ближайшего узла равна
1 + 2 + 4 + ... + 2^n = k
=> 2^n = k + 1
=> n = log(k+1)
Таким образом, k-й удаленный узел находится на высоте log(k)
Это говорит нам о том, что когда вы получаете поиск узла, расстояние которого <= logk(высота k-го узла). Мы можем ответить немедленно, поскольку мы знаем полную окрестность, и нам не нужно тратить logk шагов на получение 1 бит информации на каждом шаге, как нам нужно делать, когда запрошенный узел находится дальше.
Поэтому, когда мы ищем узел, глубина которого равна h. Вы будете запрашивать узлы, чья глубина уменьшается на 1 в худшем случае, пока не достигнете узла, для которого запрошенная глубина узла равна log k, и этот узел сможет немедленно ответить на запрос.
2. Чтобы математически ответить на ваш первый вопрос, с подавляющей вероятностью высота узлов равна O(log n)
Рассмотрим сеть, в которой ключами являются M бит, а в сети имеется N узлов. Теперь мы смотрим на дерево маршрутизации с точки зрения конкретного узла u. Это дерево будет переполнено битами более высокого порядка, поскольку 1/2 возможных ключей попадают в верхнюю корзину, 1/4 - во вторую и так далее.
So what is the probability that your first q slots
in the routing tree with distance
from 2^0 - 2^1 to 2^q-1 - 2^q are empty.
This requires that all the N nodes fall in the buckets greater than q
To select a key in bucket greater than q you
need to ensure that your maximum prefix match is less than M-q.
So there are 2^M total keys of which 2^q keys
have the same prefix of length (M-q) as the node u.
So the favourable cases are 2^M - 2^q.
Total cases are 2^M
Assume all N key draws are independent
So the probability that q lowest slots are empty is (1 - 1/2^(M-q))^N
So we plug in q = M - clog(n) which would mean
that there are clog(n) filled buckets
with M-clog(N) lower buckets empty
P = (1-1/2^(clog(N)))^N
= (1-1/N^c)^N
this is approximately equal to
1-1/N^(c-1)
Таким образом, вероятность приближается к 1 по мере увеличения c, и, скорее всего, в таблице маршрутизации будут заполнены только верхние слоты clog(n).