Skip to Content.
Sympa Menu

bluesky - Re: 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: Re: Kademlia and Pastry (was: Kademlia Kademlia Kademlia (was: how to do censorship resistance (was: Grapevine Technical Overview)))
  • Date: 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





Archive powered by MHonArc 2.6.24.

Top of Page