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 <= t

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.