Dla celów metrycznych Kademlia XOR

Question

W dokumencie Kademlia paper Petara Maymounkova i Davida Mazièresa mówi się, że odległość XOR jest poprawną wartością nie-euklidesową z ograniczonymi wytycznymi, dlaczego każda z właściwości poprawnej metryki jest konieczna lub interesująca , a mianowicie:

• d (x, x) = 0
• d (x, y)> 0, gdy x = y
• forall x, y: d (x, y) = d (y, x) - symetria
• d (x, z) < = d (x, y) + d (y, z) - nierówność trójkąta

Dlaczego pomiar ma ogólnie te właściwości? Dlaczego każda z tych właściwości jest niezbędna w kontekście routingu zapytań w implementacji tabeli skrótów Kademlia?

Ponadto, w artykule wspomniano, że jednokierunkowość (dla danego xi odległości l istnieje tylko jeden y, dla którego d (x, y) = l) gwarantuje, że wszystkie zapytania będą zbieżne wzdłuż tej samej ścieżki . Dlaczego to jest takie?

Answer 1

Mogę mówić tylko dla Kademlii, może ktoś inny może udzielić bardziej ogólnej odpowiedzi. W międzyczasie ...

• d (x, x) = 0
• d (x, y)> 0, gdy x! = Y

Te dwa punkty razem efektywnie oznaczają, że najbliższy punkt do x sam w sobie jest x; każdy inny punkt jest dalej. (To może wydawać się intuicyjne, ale inne aspekty metryki XOR nie są.)

W kontekście Kademlii jest to ważne, ponieważ wyszukiwanie węzła o ID x spowoduje, że ten węzeł będzie najbliższy. Byłoby niezręcznie, gdyby tak nie było, ponieważ wyszukiwanie zbliżające się do x może nie znaleźć węzła x.

• forall x, y: d (x, y) = d (Y, X)

Struktura tabeli routingu Kademlia jest tak, że węzły zachowania szczegółowej wiedzy o przestrzeń adresowa najbliżej nich i wykładniczo zmniejszająca znajomość bardziej odległej przestrzeni adresowej. W skrócie, węzeł próbuje zachować najdłuższe kontakty, o których słyszy.

Symetria jest przydatna, ponieważ oznacza, że ​​każdy z tych najbliższych kontaktów będzie utrzymywał szczegółową wiedzę o podobnej części przestrzeni adresowej, a nie zdalnej części.

Jeśli nie mamy tej właściwości, może być pomocne, aby wyszukiwać jako bardziej podobne do wskazówek zegara poruszającego się w jednym kierunku wokół zegara. Węzeł na godzinie 1 (Węzeł 1) jest blisko węzła 2 na godzinie 2 (30 °), ale węzeł 2 jest daleki od węzła 1 (330 °). Wyobraźmy sobie, że szukamy dwóch najbliższych do trzeciej (tzn. Node1 i Node2). Jeśli wyszukiwanie osiągnie Node2, nie będzie wiedział o Node1, ponieważ jest daleko. Całe wyszukiwanie i topologia musiałaby się zmienić.

• D (X, Z) < = D (x, y) + R (y, z)

Jeśli tak nie było, to nie byłoby możliwe do węzeł, aby wiedzieć, które kontakty z tabeli routingu mają zwrócić podczas wyszukiwania. Znałby najbliżej celu, ale nie ma żadnej gwarancji, że jeden z innych bardziej odległych kontaktów nie dałby krótszej ogólnej ścieżki.

Z powodu tej właściwości i jednokierunkowości, różne wyszukiwania rozpoczynające się od wyraźnie oddzielonych punktów będą dążyć do zejścia w dół tą samą ścieżką.

Jednokierunkowość oznacza, że ​​żadne dwa węzły nie mogą mieć tej samej odległości od danego punktu. Gdyby tak nie było, punkt docelowy mógłby być otoczony przez grupę węzłów znajdujących się w tej samej odległości od niego. Następnie różne różne wyszukiwania będą wolne od wyboru któregokolwiek z nich do przejścia. Jednak jednokierunkowość gwarantuje, że dokładnie jedna z tych grup będzie najbliższa, a każde wyszukiwanie, które wybierze między tą grupą, zawsze wybierze tę samą.

Answer 2

myślę, że może to wyjaśnić odrobinę, daj mi znać http://metaquestions.me/2014/08/01/shortest-distance-between-two-points-is-not-always-a-straight-line/

zasadzie każdy hop gdyby był tylko jeden bit w czasie w sieci pełni zaludnionych (ekstremalnych), a następnie musiałby dwukrotnie większą wiedzę na temat poprzedni przeskok. Gdy zbierzesz się, wiedza będzie większa, aż dotrzesz do najbliższych węzłów, których wiedza jest najlepsza w sieci.

Answer 3

Od pewnego czasu walę głową w głowę: w jaki sposób XOR - jak w liczbie różnych bitów, odpowiednia odległość Hamminga - może być podstawą totalnego zamówienia?

Cóż, nie może, taki wskaźnik sam w sobie nie wystarcza dla porównywalnej relacji, wszystko, co można zrobić, to zrzuty węzłów w kółko wokół punktu.

Potem czytałem gazetę bliżej i zauważyłem, że jest napisane "XOR jako wartość całkowita" i to mnie olśniło: sedno nie jest "metryką XOR", ale długość wspólnego przedrostka ID (z czego XOR jest mechanizmem pochodnym).

Weź dwa węzły o tej samej odległości Hamminga od "self" i długości ich wspólnego przedrostka "self": najkrótszy wspólny prefiks jest najdalszym węzłem.

Papier używa „XOR odległość metryczny”, ale to naprawdę powinien brzmieć „ID prefiksu długość całkowitą zamawiania”