Proprietà metriche Kademlia XOR

Question

Nel Kademlia paper di Petar Maymounkov e David Mazières, si dice che la distanza XOR è una metrica non euclidea valida con spiegazioni limitate sul motivo per cui ciascuna delle proprietà di una metrica valida è necessaria o interessante , vale a dire:

• d (x, x) = 0
• d (x, y)> 0, se x = y
• forall x, y: d (x, y) = d (y, x) - simmetria
• d (x, z) < = d (x, y) + d (y, z) - disuguaglianza triangolo

Perché è importante che una metrica abbia queste proprietà in generale? Perché ciascuna di queste proprietà è necessaria nel contesto delle query di routing nell'implementazione della tabella hash distribuita di Kademlia?

Inoltre, il documento menziona che unidirezionalità (per una data xe una distanza l, esiste solo una sola y per cui d (x, y) = l) garantisce che tutte le query convergeranno lungo lo stesso percorso . Perchè è così?

Answer 1

Posso parlare solo per Kademlia, forse qualcun altro può fornire una risposta più generale. Nel frattempo ...

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

Questi due punti insieme significano effettivamente che il punto più vicino a x è x stesso; ogni altro punto è più lontano. (Questo può sembrare intuitivo, ma altri aspetti della metrica XOR non lo sono.)

Nel contesto di Kademlia, questo è importante poiché una ricerca per nodo con ID x produrrà quel nodo come il più vicino. Sarebbe imbarazzante se non fosse il caso, dal momento che una ricerca convergente verso x potrebbe non trovare il nodo x.

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

La struttura della tabella di routing Kademlia è tale che i nodi mantengono conoscenza dettagliata della spazio di indirizzo più vicino a loro e conoscenza esponenzialmente decrescente di uno spazio di indirizzi più distante. In breve, un nodo cerca di mantenere tutti i i contatti più vicini di cui si sente parlare.

La simmetria è utile poiché significa che ciascuno di questi contatti più intimi manterrà una conoscenza dettagliata di una parte simile dello spazio degli indirizzi, piuttosto che una parte remota.

Se non avessimo questa proprietà, potrebbe essere utile pensare alla ricerca più come le lancette di un orologio che si muovono in una direzione attorno a un quadrante. Il nodo a ore 1 (Nodo1) è vicino a Nodo2 a ore 2 (30 °), ma il Nodo2 è lontano dal Nodo1 (330 °). Quindi immagina che stiamo cercando i due più vicini alle 3 (cioè Nodo1 e Nodo2). Se la ricerca raggiunge Nodo2, non conoscerà Nodo1 poiché è lontano. L'intera ricerca e la topologia dovrebbero cambiare.

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

Se questo non fosse il caso, sarebbe impossibile un nodo per sapere quali contatti della sua tabella di routing devono essere restituiti durante una ricerca. Saprebbe lo più vicino all'obiettivo, ma non ci sarebbe alcuna garanzia che uno degli altri contatti più distanti non produca un percorso complessivo più corto.

A causa di questa proprietà e di unidirezionalità, ricerche diverse a partire da punti ampiamente separati tenderanno a convergere lungo lo stesso percorso.

L'unidirezionalità indica che non è possibile che due nodi abbiano la stessa distanza da un determinato punto. Se così non fosse, allora il punto bersaglio potrebbe essere circondato da un gruppo di nodi alla stessa distanza da esso. Quindi varie ricerche potrebbero essere scelte liberamente tra quelle da passare. Tuttavia, l'unidirezionalità garantisce che esattamente uno di questi gruppi sia il più vicino e qualsiasi ricerca che sceglie tra questo gruppo selezionerà sempre la stessa.

Answer 2

Penso che questo possa spiegare un pochino, fatemelo sapere http://metaquestions.me/2014/08/01/shortest-distance-between-two-points-is-not-always-a-straight-line/

In sostanza ogni hop se fosse solo un po 'alla volta in una rete completamente popolato (estremo), allora avrebbe il doppio della conoscenza del hop precedente. Mentre convergi la conoscenza è maggiore fino ad arrivare ai nodi più vicini la cui conoscenza è massima nella rete.

Answer 3

Mi sono battuto per la testa da un po 'di tempo: come può il XOR - come nel numero di bit diversi, una distanza appropriata da Hamming - essere la base di un ordine totale?

Beh, non è possibile, una metrica di per sé non è sufficiente per una relazione comparabile, tutto ciò che può fare è eseguire il dump dei nodi in circoli attorno a un punto.

Poi ho letto il foglio più da vicino e ho notato che dice "XOR come un valore intero" e mi è venuto in mente: il punto cruciale non è la "metrica XOR", ma la lunghezza del prefisso comune dell'ID (di cui XOR è un meccanismo di derivazione.)

Prendere due nodi con la stessa distanza di Hamming da "self" e la lunghezza del loro prefisso comune a "self": quello con il prefisso comune più breve è il nodo più lontano.

La carta utilizza "distanza XOR metrica", ma in realtà dovrebbe leggere "ID prefisso lunghezza ordinamento totale"