bluesky AT lists.ibiblio.org
Subject: Global-Scale Distributed Storage Systems
List archive
- 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
-
Re: Grapevine - scalability,
Stephen Blackheath, 12/09/2001
- <Possible follow-up(s)>
- Re: Grapevine - scalability, Stephen Blackheath, 12/09/2001
- Re: Grapevine - scalability, Oskar Sandberg, 12/09/2001
- RE: Grapevine - scalability, Lucas Gonze, 12/11/2001
- RE: Grapevine - scalability, Tony Kimball, 12/11/2001
- RE: Grapevine - scalability, Lucas Gonze, 12/11/2001
- RE: Grapevine - scalability, Tony Kimball, 12/11/2001
- Re: Grapevine - scalability, Anthony Jones, 12/11/2001
Archive powered by MHonArc 2.6.24.