> Therefore, when trying to locate a node, you don't need to do an exhaustive exponential "ping all my neighbours and get all their neighbours" search; one could say that you are able to follow a vector in the hashspace.
How are you able to do this without pinging all neighbors? How do you know you've found the node with closest distance? Or is there a defined XOR result for closest distance and you can stop searching once you've found it?
You keep track of a few folks at different distances from yourself, and route packets to the folks one knows which are closest to the ultimate destination (or ask them whom they know closest to that destination).
So rather than asking everyone you know, who ask everyone they know, who ask everyone they know, you're asking a subset, who ask a subset, who ask a subset.
The latter, as far as I take it. That is, each given Kademlia-based system defines a 'close-enough' / neighbourhood constant. If a given result from xor is <= that constant, you have reached your destination. Because obviously, you won't have node IDs actually matching your target (e.g. file) hash (assuming no hash collisions.) So you need a 'proximity' value.
Granted, the whole picture is more complex, and my knowledge is very limited. A node that wants to search for something sends its search query to the neighbour closest to target, which then, as I understand, propagates / rebroadcasts that query to its neighbour which itself is closest to destination. There seems to be some redundancy involved / multiple paths taken, perhaps to ensure that all nodes within that proximity distance are found. (So for example there could be multiple nodes storing the same key (say, file hash), but with different values (different node IDs (for nodes that actually have the file in question.))) I'm being vague though, that's very true..
But as I understand it, as long as the whole graph of nodes is connected, with no orphan sub-graphs forming / detaching (something which may not be trivial to accomplish/ensure), you should be able to get all relevant key->value pairs / reach all relevant nodes in your search. The way the search is concluded in Gnutella (I think) is that each target node responds by connecting to the source/query-issuing node directly (every query carries with it source UDP IP:port (I think)).
edit / P.S.: also, it may be that a given node stores node IDs in its proximity range (the 'close enough' value), but I'm not sure of this; I'm adding this because it may actually help ensure that all nodes / key->value pairs of interest are accounted for, i.e. it's a worthwhile idea anyway.
How are you able to do this without pinging all neighbors? How do you know you've found the node with closest distance? Or is there a defined XOR result for closest distance and you can stop searching once you've found it?