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

Question

Он сказал:

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

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

Answer 1

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

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

Затем аргументы далее вниз основаны на этой основанной на ведре проекции.

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

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

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