Skip to Content.
Sympa Menu

bluesky - Re: 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: Ted Anderson <TedAnderson AT mindspring.com>
  • To: Global-Scale Distributed Storage Systems <bluesky AT franklin.oit.unc.edu>
  • Subject: Re: Kademlia Kademlia Kademlia (was: how to do censorship resistance (was: Grapevine Technical Overview))
  • Date: Thu, 30 May 2002 22:16:24 -0400


Zooko wrote:
> 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?

My prose was not too clear. I don't really define "close" on these
160-bit ids, but I had in mind close when treated as a binary integer.
The result, I think, is that successive elements of the routing array
should match the local node id in one additional bit position. The bits
below the complemented one are essentially arbitrary. In fact, it is
better to use some other metric than closeness below this complemented
bit, such as reliability or latency.

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

I think the key point here, and in some of the subsequent discussion, is
that the hypercube is *vastly* sparse. Linking the extant nodes
necessarily requires ignoring most of the bits of the node id. Using an
array-like structure, where larger indexes match more bits, essentially
maps the existing nodes into a tree.

I must say the interlocked trees interpretation of Plaxton tooks me a
while to figure out. I have always thought of it as a hypecube, even
though its massive sparseness, makes the tree model more physical. I
guess the large variety of interpretations of this basic idea makes its
acceptance more difficult.

> 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.".

Given the binary integer definition of closeness, I think the two
approaches are equivalent.

> 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.

The hamming distance, counting ones in the XOR, gives the distance in a
fully populated hypercube. But since it is sparse, a hierarchical
approach should be robust. As Oskar and others point out, the fact that
(esp. at the top of the tree) there are many routing choices, should
allow for efficient, reliable routing as long as the choice of which
peers to select for each bucket in the routing table matches reality.
In the case of many transient nodes, it may be that reliability, age or
longevity are better metrics than network proximity.

> (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.)

Indeed. The need for backtracking to find data should be limited
assuming nodes collect matching chunks aggressively enough and there is
enough overlap (shadowing) to handle nodes dropping out of the network.

Ted





Archive powered by MHonArc 2.6.24.

Top of Page