Как понять временную сложность работы узла Kademlia

Question

Теперь я изучаю сеть Kademlia, читая классическую бумагу Kademlia: A Peer-to-peer Information System Based on the XOR Metric. Я хочу понять сложность его работы, но до сих пор не могу понять.

В 3 Эскиз доказательства секции, бумага дает два определения:

1. Глубина узла (Н): 160 - I, где я является наименьшим показателем Беспоставочной -empty ведро
2. высота ковша Node Y в узле х: индекс ведра, в котором х вставил бы у минус индекс не менее значительного пустого ведра иксы.

И три вывода:

1. С подавляющей вероятностью высота любого заданного узла будет в постоянной журнале п ​​ для системы с п узлами.
2. Высота ковша ближайшего узла к идентификатору в ближайшем к k-узле узле будет находиться в пределах константы log k.
3. Если ни один из этих узлов h не является самым значимым k-ведрами, процедура поиска найдет узел наполовину близкий (точнее, расстояние которого на один бит короче) на каждом шаге и, таким образом, включит узел в h - log k шаги.

Так что мои вопросы:

1. Что такое «наименее значащий пустое ведро» и «наиболее значимых к-ковши»?
2. Как объяснить глубину и высота ковша визуально?
3. Как понять второй и третий выводы, скажем, почему log k и h - log k?

Answer 1

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

---

Что такое «наименее значащий пустое ведро» и «наиболее значимых к-ковши»?

Это в основном относится к ведрами, отсортированных по XOR расстояния по отношению к идентификатору узла

Как объяснить глубину и ковшовый высоту в наглядном виде?

Каждое ведро покрывает область пространства ключей. Например. от 0x0000 ^{упрощен до 2 байтов} до 0x0FFF для 1/16-го пространства ключей. Это может быть выражено в CIDR-подобных масках, 0x0/4 (4 бита префикса). Это более или менее глубина ведра.

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

Упрощенная реализация может вместо этого использовать массив с фиксированной длиной и поместить каждый ковш в положение общих битов префикса относительно собственного идентификатора узла. То есть позиция 0 в массиве будет иметь 0 разделяемых битов префикса, это самый отдаленный ведро, ведро покрывает 50% пространства ключей и ведро, где самый старший бит - это инвертированный MSB собственного идентификатора узла.

В этом случае глубина - это просто позиция массива.

Как понять второй и третий выводы, скажем, почему log k и h - log k?

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

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

Промыть, повторить до тех пор, пока не будет найдено более узких узлов.

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

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

Так к является константой (узлы-за ведро) так бревно к. Двойное количество узлов в ведре, и оно будет иметь удвоенное разрешение данной области пространства ключей и, таким образом, (вероятностно) даст узел, который на один бит ближе к цели, чем ведро с размером k/2. То есть вам нужно удвоить количество записей на каждый бит для каждого дополнительного бита на хоп, который вы хотите сохранить.

---

Edit: Вот визуализация фактического односетевых битторрент таблицы DHT маршрутизации, отсортированных по их префиксов, т.е. не относительно локального узла ID:

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