Kademlia Kademlia Kademlia (was: how to do censorship resistance (was: Grapevine Technical Overview))

Zooko Zooko <zooko@zooko.com>
Wed, 29 May 2002 05:59:32 -0700



 Bram wrote:
>
> Ted Anderson wrote:
> 
> > This Kademlia sounds very much like the boolean n-cube routing scheme
> > I've been touting for a while now.  I sent a description of it to one of
> > the Freenet lists around 10/1999, at the paragraph starting "The core of
> > my solution..." in [1].  Kademlia sounds like good stuff and David
> > Mazi=E8res has been involved in several interesting projects.
> 
> Yep, that's the exact same distance function as kademlia uses. That
> distincae function, by the way, has been reinvented by several people.

Actually my reading of Ted's letter [1] says that his proposal was, like 
Bram's, an n-dimensional hypercube (n=160).  Did I get that right, Ted, Bram?

The Kademlia metric as I understand it from this paper [2] yields a very 
different structure -- a binary tree.

The difference in the way the metric is computed is that Ted's says "I want to 
know 160 peers, each of which has the same ID as me except for its i'th bit 
being different.", and Kademlia's says "I want to know up to 160 peers, each 
of which has the same i-1 most significant bits and a different i'th bit.".  

I've heard of hypercube routing notion from many people over the years, but 
the Kademlia notion was novel to me when I saw their paper at the Peer to 
Peer Workshop.


> I find it odd that viewing the xor as a number is intuitive to everyone
> else while adding up the number of 1s in it is intuitive to me. Maybe
> everyone else is optimizing for analyzability while I'm optimizing for
> simplicity and robustness, trying to get away from a heirarchical
> structure.

Well, the Kademlia structure ("as a number") is much more robust than the 
hypercube structure ("adding up the number of 1s" == Hamming distance), 
because it imposes a relatively loose constraint on which nodes a given node 
can peer with.  In the hypercube structure, there is exactly one ID out of all 
possible IDs that could be your i'th peer.  In the binary tree structure, any 
id which matches your most-significant i-1 bits is a legitimate i'th peer.

For example, if there are 2^20 total nodes in a hypercube network, chances are 
that none of them will satisfy the strict requirement to be your 4th peer 
(your peer for i=4).  Therefore you have to use an approximate match (as Ted's 
proposal allows) that is "close" (by the same measure).  This leaves me 
wondering if the overall hypercube-like structure is still going to have 
efficient routing properties when using approximate matches like that, and at 
the same time whether the approximate match shadowing a more precise match 
could cause problems.

In a binary tree (Kademlia) network of size 2^20, there are 2^15 nodes which 
are all equally legitimate to be your 4th peer.  The claims about routing 
efficiency and correctness are all justified based on the assumption that you 
can communicate with *any* one of these 2^15 nodes.  Now that's robust!

Of course, once you get down to i=12 then this is no longer so easy -- now 
there are only 2^7 nodes in the entire network who would qualify.  I think 
that this is still more robust than other proposals for two reasons:

1.  There are 2^8 - 1 other nodes ("parallel" to you) who are equivalently 
qualified as you are to find the next hop.  The query can try more than one of 
these, in parallel or in series.  (In fact, it is free to pre-emptively choose 
among these 2^8 nodes on some other basis such as reliability or latency.)

2.  The case that the query fails to find the appropriate next-hop will 
necessarily be handled in the same way as the case that said node has exited 
the network.  That is: one or more of the "current hop" nodes will be 
responsible for the ID space covered by the absent next-hop nodes.  This is an 
approximation which can cause shadowing (like the use of close matches in the 
hypercube), but it is purely local -- no query will be effected by this 
appromixation unless its target ID is in this particular 2^-13 sliver of the 
ID space.

(Purely local approximations which might cause shadowing are necessary in any 
possible network.  Consider the case that there are only 2^12 nodes in the 
network.  Now you are unable to find a node to serve as your i=12 peer, but 
that's because you are the one responsible for the associated ID space.)


Hm.  This suggests a twist to Kademlia:

If a node doesn't have the data you are looking for, and it also doesn't know 
any other nodes that are closer to the ID, then call it a "failed leaf node" 
with respect to this query.  When a node responds to a previous-hop node, 
telling the previous-hop node that the object it sought couldn't be found, it 
includes a count of the number of failed leaf nodes who have been queried 
(counting itself, so always at least 1).  As long as the count is less than a 
constant K (which, I guess, should be something like 8), then the previous-
node continues the search, by asking other next-nodes.  If it has tried all of 
the appropriate next-nodes that it knows, then it sends a failure message to 
*its* previous node with the failed-leaf-node count.

This is a little mini-flood which cannot impose much bandwidth cost (but can 
impose much latency!) and greatly reduces the risk of a false negative due to 
a broken route.

You can of course do a similar trick on publication of data to ensure 
replication onto the K closest reachable nodes.


Regards,

Zooko

-------
Secure Distributed Systems Consulting -- http://zooko.com/
-------

[1] http://www.transarc.ibm.com/~ota/datadist-19991026.txt
[2] http://kademlia.scs.cs.nyu.edu/kpos.pdf