bluesky AT lists.ibiblio.org
Subject: Global-Scale Distributed Storage Systems
List archive
- 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-----
-
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.