Что означает высота ковша в газете Kademlia?

Question

Там сказано:

Начнем с некоторых определений.Для k-сегмента, покрывающего диапазон расстояний 2i, 2i + 1, определите индекс блока, равный i.Определите глубину h узла, равную 160 - i, где i - наименьший индекс непустого сегмента.Определите высоту сегмента y узла в узле x как индекс сегмента, в который x будет вставлять y минус индекс наименее значимого пустого сегмента x.Поскольку идентификаторы узлов выбираются случайным образом, из этого следует, что сильно неоднородные распределения маловероятны.Таким образом, с подавляющей вероятностью высота любого данного узла будет в пределах константы log n для системы с n узлами.Более того, высота сегмента ближайшего узла к идентификатору в k-м ближайшем узле, вероятно, будет в пределах константы log k.

Я могу понять определение высоты сегмента, но я неЯ не знаю, зачем нам это определение, и я не понимаю последнее предложение абзаца.

---

Обновления: я также думаю, что в статье есть опечатка: высота корзины должна быть индексомсегмент, содержащий y минус индекс наименее значимого пустого сегмента «N-».Я не прав?

Answer 1

но я не знаю, зачем нам это определение

Аргумент эффективности O (log n) для kademlia с точки зрения размера таблицы маршрутизации и шагов поиска основан на отображениивсе пространство ключей из n узлов в k-сегменты, где более отдаленные области охватывают экспоненциально большие доли пространства ключей.Эффективно сжимая всю сеть в смещенный список выборок.

Затем аргументы, расположенные ниже, основываются на этой проекции на основе сегмента.

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

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

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