Цели на метричните свойства на Kademlia XOR

Мога да говоря само за Kademlia, може би някой друг може да даде по-общ отговор. Междувременно...

• d(x,x) = 0
• d(x,y) > 0, if x != y

Тези две точки заедно ефективно означават, че най-близката точка до x е самата x; всяка друга точка е по-далеч. (Това може да изглежда интуитивно, но други аспекти на метриката XOR не са.)

В контекста на Kademlia това е важно, тъй като търсенето на възел с ID x ще даде този възел като най-близкия. Би било неудобно, ако това не беше така, тъй като търсенето, сближаващо се към x, може да не намери възел x.

• за всички x,y : d(x,y) = d(y,x)

Структурата на таблицата за маршрутизиране на Kademlia е такава, че възлите поддържат подробна информация за адресното пространство, което е най-близо до тях, и експоненциално намаляващо познаване на по-отдалеченото адресно пространство. Накратко, възел се опитва да запази всички най-близките k контакти, за които чува.

Симетрията е полезна, тъй като означава, че всеки от тези най-близки контакти ще поддържа подробни познания за подобна част от адресното пространство, а не за отдалечена част.

Ако нямахме това свойство, може да е полезно да мислим за търсенето като повече като стрелките на часовник, движещи се в една посока около циферблата. Възелът на 1 часа (Node1) е близо до Node2 на 2 часа (30°), но Node2 е далеч от Node1 (330°). Представете си, че търсим двата най-близки до 3 часа (т.е. възел 1 и възел 2). Ако търсенето достигне Node2, то няма да знае за Node1, тъй като е далеч. Цялото търсене и топология ще трябва да се променят.

• d(x,z) <= d(x,y) + d(y,z)

Ако това не беше така, щеше да е невъзможно възелът да знае кои контакти от своята таблица за маршрутизиране да върне по време на търсене. Той ще знае k, който е най-близо до целта, но няма да има гаранция, че някой от другите по-отдалечени контакти няма да доведе до по-къс общ път.

Поради това свойство и еднопосочност, различни търсения, започващи от значително разделени точки, ще имат тенденция да се събират по един и същи път.

Еднопосочността означава, че два възела не могат да имат еднакво разстояние от дадена точка. Ако това не беше така, тогава целевата точка можеше да бъде заобиколена от куп възли на същото разстояние от нея. Тогава различни различни търсения ще бъдат безплатни, изберете някое от тях, през което да преминете. Въпреки това, еднопосочността гарантира, че точно един от тази група ще бъде най-близкият и всяко търсене, което избира между тази група, винаги ще избира същата.

От известно време си блъскам главата по този въпрос: как може XOR - както в броя на различните битове, правилното разстояние на Хеминг - да бъде в основата на общ ред?

Е, не може, такава метрика сама по себе си не е достатъчна за сравнима връзка, всичко, което може да направи, е да изхвърля възли в кръгове около точка.

След това прочетох статията по-внимателно и забелязах, че се казва „XOR като цяло число“ и ми просветна: същността не е „метриката XOR“, а дължината на общия префикс на ID (от които XOR е механизъм за извличане.)

Вземете два възела с еднакво разстояние на Хеминг от „self“ и дължината на техния префикс, общ за „self“: този с най-къс общ префикс е най-отдалеченият възел.

Хартията използва „метрика за разстояние XOR“, но наистина трябва да се чете „Общо подреждане на дължината на префикса на ID“

Мисля, че това може да го обясни донякъде, уведомете ме http://metaquestions.me/2014/08/01/shortest-distance-between-two-points-is-not-always-a-straight-line/

По принцип всеки скок, ако беше само един бит в даден момент в напълно запълнена мрежа (екстремно), тогава щеше да има два пъти повече знания от предишния скок. Докато се сближавате, знанието е по-голямо, докато стигнете до най-близките възли, чието познание е най-важното в мрежата.