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: Oskar Sandberg <oskar AT freenetproject.org>
  • To: Global-Scale Distributed Storage Systems <bluesky AT franklin.metalab.unc.edu>
  • Subject: Re: Kademlia Kademlia Kademlia (was: how to do censorship resistance (was: Grapevine Technical Overview))
  • Date: Thu, 30 May 2002 13:14:38 +0200


On Wed, May 29, 2002 at 05:59:32AM -0700, 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?
>
> 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.

The much cited system proposed by Plaxton [1] works this way, and it's
derivatives used in systems like Oceanstore and PAST [2][3] as well. By
only routing "forward" on the key (only matching the previous levels at
each level, rather than all the others), you get more flexibility in
choosing your neighbors (which the cited systems use to choose network
topologically close neighbors) at no real cost. I was not aware that
anyone was proposing a distributed system to route in a strict hypercube
which are really more suited connecting processors and other very static
nodes.

Hypercube routing can be seen as a bunch of interlocked trees as well.
They are just different ways of visualizing the topology.

Unless Kademlia brings something else to the table, that sounds like old
news to me.

--


[1] C. Plaxton, R. Rajaraman, A Richa. Accessing Nearby copies of
replicated objects in a distributed environment. In Proc. of ACM SPAA,
June 1997.

[2] J Kubiatowcz, D Bindel, Y Chen, S Czerwinski, P Eaton, D Geels, R
Gummandi, S Rhea, H Weatherspoon, W Weirner, C Wells, B Zhao.
Oceanstore: An architecture for Global Scale Persistant Storage. In
Proc. ASPLOS'2000, November 2000.

[3] A Rowstron, P Druschel. Pastry: Scalable, distributed object
location and routing for large-scale peer-to-peer systems. Microsoft
Research, submission to ACM HOTOS VIII, 2001.



--

Oskar Sandberg
oskar AT freenetproject.org




Archive powered by MHonArc 2.6.24.

Top of Page