Skip to Content.
Sympa Menu

bluesky - Kademlia and Pastry (was: 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: Oskar Sandberg <oskar AT freenetproject.org>, Global-Scale Distributed Storage Systems <bluesky AT franklin.metalab.unc.edu>
  • Subject: Kademlia and Pastry (was: Kademlia Kademlia Kademlia (was: how to do censorship resistance (was: Grapevine Technical Overview)))
  • Date: Thu, 30 May 2002 05:43:40 -0700



[I, Zooko, wrote the lines prepended with '> > '. And the ones without any
prepended greater-than signs, too.]

Oskar wrote:
>
> > 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. [... ellided by Zooko]
[...]
> Unless Kademlia brings something else to the table, that sounds like old
> news to me.


Hm. Yes, you are right that Kademlia's routing is really the same as that in
e.g. Pastry. To their credit, the authors of Kademlia say as much in their
paper.

Although I had read the Pastry paper, I didn't understand the advantages of
the routing system over e.g. Chord. (In fact, one of the authors of Pastry
tried to convince me that Pastry had a qualitative technical advantage over
Chord, due to its ability to incorporate network proximity. Unfortunately
for
him and for my education, I didn't care very much about network proximity.
More on that below.)


There are several reason why I didn't appreciate the XOR metric even after
I read the Pastry paper, and that they are worth looking at. They show, for
me at least, some added conceptual value that Kademlia has brought to the
table.

1. The Pastry paper describes the technique as successive approximation by
appending digits and popping about on a circle. The Kademlia paper describes
it (the very same operation) as XOR and traversing a binary tree. I find the
latter much more intuitive.

2. The Pastry paper includes a "shift gears" step in which you use a
different routing system once you've gotten close enough using the XOR
routing
system. The Kademlia paper uses only the XOR routing system "all the way
down".

(By the way, now that I've understood the XOR routing system, I appreciate
*why* the Pastry design includes a second technique for the last few hops.
Kademlia needs to solve the same problem, and it currently attempts to do so
by returning redundant query results...)

3. The Pastry paper never mentions these two interesting properties of XOR
routing: that it is both symmetric and unidirectional. The Kademlia paper
makes these two points explicitly, and I realized that the routing system
offered these properties when reading the Kademlia paper.

(By the way, symmetric isn't a big deal with regard to efficiency -- it's
just
a factor of 2 -- but it might be a bigger deal with regard to bypassing
firewalls, which are usually asymmetric in blocking initiation of
TCP connections...)

4. The Pastry paper *does* mention the third interesting property of this
routing system: next-hop-selection (i.e., that there are a large number of
valid next hops, and you may choose among them on some criteria other than
routing), but the Pastry paper repeatedly emphasizes that this property is
used for network proximity, which I care relatively little about. The
Kademlia paper uses the same property for reliability (and, secondarily, for
low latency), which I care a lot more about.

(By the way, I am now thinking about using that property for the
generalization of reliability: trustworthiness...)


Regards,

Zooko

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




Archive powered by MHonArc 2.6.24.

Top of Page