Skip to Content.
Sympa Menu

bluesky - Re: Grapevine - scalability

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.oit.unc.edu>
  • Subject: Re: Grapevine - scalability
  • Date: Mon, 10 Dec 2001 00:59:32 +0100


On Mon, Dec 10, 2001 at 11:15:17AM +1300, Stephen Blackheath wrote:
> On Mon, 10 Dec 2001 10:12, Oskar wrote:
<>
> I haven't thought about scalability for a while, so I probably slightly
> misrepresented my project.
>
> Grapevine is based on multi-dimensional space. Like "Content Addressable
> Network", the scalability of Grapevine is much worse than log(N) / p, but
> it
> is consistent. It is O(N^(1/d)) where I commonly assume d is 6, and the
> number of neighbours is 118. For 1,000,000 neighbours in 6-dimensional
> space, it will take approximately 10 hops to reach any point. For
> 1,000,000,000 nodes, it will take 31 hops.

I'm assuming the "CAN" you are refering to is [1] (the authors of that
paper seem to mean for "CAN" to be a general term). That algorithm is
actually more or less equivalent to Plaxton and co, except that rather
than fixing the grid size and increasing the number of dimensions as N
grows, it fixes the number of dimensions and increases the gridsize (the
effect of "splitting the zone") which leads to considerably worse
scalability.

That paper also contains exactly the sort of handwaving toward the real
problems brought on by trying to make a rigid grid of fickle nodes that
I just don't buy. It acknowledges that there are a number of ways for
the network to become inconsistent, but waves it off with a couple of
scary sounding lines about "controlled floods". And not to mention the
constant need to defragment the network, with their tagged on background
algorithm in the appendix not sounding very fun to implement to me.

I'm not saying it cannot work, but personally I will keep trying to get
the correct emergent properties out of networks consisting of nodes
behaving under a simple set of rules to the grave sooner than give in to
the nightmare of trying to keep this sort of network consistant in the
wild.

<>

[1] http://www.acm.org/sigs/sigcomm/sigcomm2001/p13-ratnasamy.pdf

--

Oskar Sandberg
oskar AT freenetproject.org




Archive powered by MHonArc 2.6.24.

Top of Page