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

Он сказал:

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

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

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


kademlia
person Adrian Liu    schedule 07.02.2019    source источник
comment
связанные: stackoverflow.com/q/29004769/1362755   -  person the8472    schedule 01.03.2019

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

person the8472    schedule 28.02.2019
comment
Я понимаю макет k-buckets, но я не понимаю, как здесь работает определение высоты сегмента. Например, высота ведра узла y равна 10, что возможно для любого k. Я не понимаю, как это может быть связано с k. - person Adrian Liu; 08.03.2019
comment
домашнее ведро по существу исчерпывающее. удвоение k означает, что на 1 бит меньше глубины, чтобы он был исчерпывающим, тем самым уменьшая глубину домашнего ведра и, следовательно, высоту, которую может иметь любое ведро относительно него. - person the8472; 09.03.2019
comment
Я думаю, вы могли бы иметь в виду своего рода динамическое разделяющее ведро. Но здесь ведро i не связано с k, оно просто определяется расстоянием. Таким образом, ведро узла y будет равно 10, если расстояние до узла x находится между 1024 и 2048, независимо от значения k. - person Adrian Liu; 11.03.2019
comment
вы правы, это потенциально другое k, чем размер ведра. Возможно, они говорят о том, что, поскольку высота растет логарифмически, все соседи будут сгруппированы вокруг самого глубокого ведра, и вам придется экспотенциировать расстояние, чтобы покрыть ~ постоянное расстояние в таблице маршрутизации, то есть оно демонстрирует локальность. Что является обязательным условием для их следующего, немного более строгого предположения. Немного раздражает дикая перегрузка переменных от одного предложения к другому. - person the8472; 11.03.2019
comment
А, теперь я понимаю вашу точку зрения, и k — это не размер ведра, а k ближайших узлов к данному узлу x. - person Adrian Liu; 15.03.2019
comment
Я обновил свой вопрос, так как думаю, что у авторов статьи была опечатка в определении высоты ковша. Не могли бы вы уточнить? Спасибо. - person Adrian Liu; 15.03.2019
comment
Возможно, это опечатка. Либо наименее значимое непустое, либо наиболее значимое пустое ведро в пространстве расстояний определяет границу, поскольку эти области должны быть приблизительно непрерывными. Если вы не инвертируете расстояние, вам придется поменять местами условия. Они ходят туда и обратно между расстоянием и обратным расстоянием несколько раз. - person the8472; 15.03.2019