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 09:08:39 -0700



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

 Oskar wrote:
>
> After having
> worked on implementing it though, I am not fond of any of these systems.
> It proved very difficult and costly to make these networks stay
> consistant under the high node churn scenarios I used for my Freenet
> simulations. [... ellided by Zooko]

Yep.  This is exactly why using the "free-choice" feature for proximity 
routing is sort of mildly interesting, but using it for reliability is very 
interesting.  My paper at IPTPS02 [1] detailed the kind of churn observed in 
practice in Mojo Nation.  I would love to get some similar stats from you 
about Freenet.

> > 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.
> 
> That is a matter of your personal taste. I find approaching the problem
> from a hypercube more intuitive. [... ellided by Zooko]

Indeed.  My personal taste is likely shared with many hackers who like me are 
more familiar with XOR and binary trees than with hyperdimensional cuboids.

> > 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.
> 
> I'm not sure what you mean by either. [... ellided by Zooko]

Perhaps you ought to read the Kademlia paper.

> The measure for "network promixity" as used by Plaxton [3] was not
> defined, it can be any metric on the network, including latency. The
> Oceanstore papers deal with extensively with reliability.

Defining "network proximity" as latency is natural enough, but defining it as 
reliability seems quite a stretch.  ;-)

Indeed the Oceanstore papers have dealt extensively with reliability, but they 
have not suggested the option of using reliability as the selection criterion 
among valid next-hop nodes.  (Instead, like Pastry, they propose that network 
proximity gets the benefit of that role, and they layer reliability at higher 
layers.)


Regards,

Zooko

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

[1] http://zooko.com/IPTPS02.pdf