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: Stephen Blackheath <stephen AT blacksapphire.com>
  • To: "Global-Scale Distributed Storage Systems" <bluesky AT franklin.oit.unc.edu>
  • Subject: Re: Grapevine - scalability
  • Date: Mon, 10 Dec 2001 11:15:17 +1300


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

On Mon, 10 Dec 2001 10:12, Oskar wrote:
> On Thu, Dec 06, 2001 at 01:32:54PM +1300, Stephen Blackheath wrote:
> > Grapevine and Freenet both work by the '6 degrees of separation' theory:
> > If you have 100 neighbours, say, and the network has 1,000,000 nodes,
> > then in an optimally connected network, you should be able to get to any
> > point in 3 hops.
>
> I think the "6 degrees" theory has more to do with shortest pathlengths
> in fixed random graphs than exponents - small world networks and all
> that. There are proofs [1] to show that pretty much all random networks
> have a logarithmic minimum pathlength between nodes, but that is rather
> different from our situation of being able to control the graph
> structure but wanting to be able to _find_ those paths.
>
> Reaching 1,000,000 within 3 hops of 100 neighbors would imply starting
> from the root of a balanced tree, but since you need to be able to start
> at any of the nodes, you need more than one tree (in graph theory terms,
> a spanning tree cannot be balanced at every node). The Plaxton model is
> to have every node act as a part of K trees, and to have K sets of
> neighbors as the children depending on whether it is reached on the 1st,
> 2nd ... Kth step. That gives
>
> log(N) / p
>
> steps for
>
> log(N) * 2^p
>
> neighbors at each node. I would be hard pressed to believe it is
> possible to do better than that.

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.

Now that I've corrected what I said, I think you'll find it a bit more
plausible.

> In my experience, a rigid structure is a nightmare. All the examples of
> attempts to route within a rigid structure that I have seen have started
> out as lovely models, but been forced into more and more elaborate
> schemes in order to protect the integrity of the rigid structure - [2]
> goes as far as to recommend rebuilding the entire graph structure once
> every 24 hours.

Grapevine bears no resemblance to OceanStore, so the "rigidity" of it is not
comparable. I certainly never need to re-build the graph structure.

> BTW, now that the the movie is almost out, how are we gonna know which
> orc is you?

I'm so ugly, I didn't need to wear a mask! (I think my scene is in the third
film, actually. LOTR is competely in post-production now.)


Steve
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQE8E+J17I0ehz47OHERAmPCAKDQq1zOZ0RIi7Qz/QX9Tkoa/mC+zwCeMFM6
ifApBhtwcGJQuBiSFIBOTG4=
=nqqJ
-----END PGP SIGNATURE-----




Archive powered by MHonArc 2.6.24.

Top of Page