Skip to Content.
Sympa Menu

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

bluesky AT lists.ibiblio.org

Subject: Global-Scale Distributed Storage Systems

List archive

Chronological Thread  
  • From: Zooko <zooko AT zooko.com>
  • To: "Global-Scale Distributed Storage Systems" <bluesky AT franklin.oit.unc.edu>
  • Subject: Kademlia Kademlia Kademlia (was: how to do censorship resistance (was: Grapevine Technical Overview))
  • Date: 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




Archive powered by MHonArc 2.6.24.

Top of Page