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:33:26 +1300


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

On Mon, 10 Dec 2001 11:15, you wrote:
> 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.

...And I missed one important detail. It's actually very approximately (but
consistently) 5 hops at 1,000,000 nodes, because when routing from point A to
point B, the farthest distance you will travel is half-way across space. If
you're further away than that, then it's shorter to travel in the opposite
direction, since space wraps around.

Similarly, 16 hops for a network of 1,000,000,000 nodes.


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

iD8DBQE8E+a27I0ehz47OHERAlVuAKDHK3MB6Z/z9RQ+b6rspYAZGXMPQgCfbGC+
2gFT79W+/1BPHge9zshDtz4=
=O+lL
-----END PGP SIGNATURE-----




Archive powered by MHonArc 2.6.24.

Top of Page