[mnet-devel] notes about new-NEW-fangled emergent networks

[Zooko]

I just discovered Naor's "Novel Architectures for P2P Applications: the 
Continuous-Discrete Approach" [1], and Kaashoek&Karger's "Koorde" [2].

Each is an emergent network that offers logarithmic dilation ("dilation" is 
basically the length of the paths in terms of number of hops) just as Chord, 
Kademlia, et al. do, but *constant* linkage (the number of links that each 
node must maintain) instead of logarithmic!

That means for a network of *any* size, each node needs to maintain only a 
small fixed number of links to peers.  (In the Naor design, the small fixed 
number is "6" for most nodes.)

Aside from the sheer wonderment of it all, there are two interesting potential 
uses for these:

1.  If you go ahead and maintain more than the required minimum linkage, you 
can get better dilation (log n / log log n) and better robustness than with 
Kademlia et al.  Actually, the same can probably be said for Kademlia et 
al. -- that maintaining extra links above the minimum can increase robustness 
and reduce dilation -- but with the new constant-linkage nets, the minimum is 
smaller!

2.  Can this be used to deploy the emergent network on an incompletely 
connected underlay graph?  For example, if you need only 6 links, could you 
link to your six best friends?  Well, unfortunately there is no "free choice" 
in these peers the way that Kademlia/Pastry offers a "free choice" about which 
peer you choose in the far-away kbuckets.  So it isn't obvious how one could 
use the new constant-degree nets to map onto more difficult underlay nets, but 
it remains intriguing.

The Koorde paper is much simpler and much more readable than the Naor paper, 
so start with that one.

--Z

P.S.  I'm not going to start implementing any new-NEW-fangled emergent 
networks until we finish ent *and* a bunch of unit tests (== an entire 
simulated network) which we can use to evaluate the new-NEW-fangled net.

P.P.S.  I've got the simulator/unit-tester partially written on the "newnet" 
branch [3].

[1] http://www.wisdom.weizmann.ac.il/~naor/topic.html#Distributed%20Computing
[2] http://iptps03.cs.berkeley.edu/program.html
[3] http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/mnet/mnet_new/mnetlib/test/Attic/test_ent.py?rev=1.1.2.1&hideattic=0&content-type=text/vnd.viewcvs-markup



-------------------------------------------------------
This SF.net email is sponsored by: If flattening out C++ or Java
code to make your application fit in a relational database is painful, 
don't do it! Check out ObjectStore. Now part of Progress Software.
http://www.objectstore.net/sourceforge
_______________________________________________
mnet-devel mailing list
mnet-devel at lists.sourceforge.net
https://lists.sourceforge.net/lists/listinfo/mnet-devel