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-----