Grapevine - scalability

Stephen Blackheath stephen@blacksapphire.com
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-----