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

Zooko Zooko <zooko@zooko.com>
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/
-------