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: Oskar Sandberg <oskar AT freenetproject.org>
  • To: 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 17:19:25 +0200


On Thu, May 30, 2002 at 05:43:40AM -0700, Zooko wrote:
> Oskar wrote:
< >
> > 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.)

I don't consider Pastry to be the best or most elegant of the various
proposed systems derived from the Plaxton paper. The system Oceanstore
uses (which they call Tapestry [1]) is probably nicer. 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. It may have been my fault, but my current hypothesis is
that these things may work in a controlled environment such a corporate
network, but will be difficult to make a work in the wild where nodes
are fickle and unreliable.

<>
> 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. However, [2] says:

"The key observation to make from Figure 3 is that the links
form a series of random embedded trees, with each node as the
root of one of these trees. As a result, the neighbor links can be
used to route from anywhere to a given node, simply by resolving
the node's address one link at a time--first a level-one link, then
a level-two link, etc."

So this not a new way of looking at it either.

> 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. But again, Pastry is not the only
paper to have covered this ground previously.

> 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.

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.

--

[1] B Zhao, J Kubiatowcz, A Joseph. Tapestry: An Infrastructure for
Fault-tolerant Wide-area Location and Routing. EECS Report No.
UCB/CSD-01-1141, Univeristy of California, Berkley, April 2001.

[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] C. Plaxton, R. Rajaraman, A Richa. Accessing Nearby copies of
replicated objects in a distributed environment. In Proc. of ACM SPAA,
June 1997.


--

Oskar Sandberg
oskar AT freenetproject.org




Archive powered by MHonArc 2.6.24.

Top of Page