[Gzz-commits] gzz/Documentation/misc/hemppah-progradu researc...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      03/01/23 09:09:13

Modified files:
        Documentation/misc/hemppah-progradu: research_problems 

Log message:
        Summary table: # of network connections

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/gzz/gzz/Documentation/misc/hemppah-progradu/research_problems.diff?tr1=1.29&tr2=1.30&r1=text&r2=text

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.29 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.30
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.29      Thu Jan 
23 07:02:30 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Thu Jan 23 
09:09:13 2003
@@ -140,30 +140,30 @@
 
 This summary table is far from complete (and from total truth)
 
-               Insert/Delete   Space           Search
-Chord:                 O(log^2 n)      O(log n)        O(log n)
-CAN:           O(r)            O(r)            O(rn^(1/r)), where r is the 
number of dimensions used in a virtual space
-Pastry:        O(log^2 n)      O(log n)        O(log n)
-Tapestry:      O(log^2 n)      O(log n)        O(log n)
-Kademlia:      O(log n)*       O(log n)        O(log n)
-Viceroy:       O(log n)        O(1)            O(log n)
-Small Worlds 1):O(1)           O(1)            O(log^2 n)
-Flooding:      N/A**           N/A**           O(n)**
-Hybrid:                N/A             N/A             N/A
-Social:                N/A***          N/A***          N/A***
-Skip graphs 1): O(log n)       O(log n)        O(log n)
-Symphony:      O(log^2 n)      O(log n)****    O(log n)
+Protocol:      Insert/Delete   Space           Search          # of network 
connections
+Chord:                 O(log^2 n)      O(log n)        O(log n)        2(log n)
+CAN:           O(d)            O(d)            O(dn^(1/d))     2d
+Pastry:        O(log^2 n)      O(log n)        O(log n)        (2^b - 1)(log 
n)/b 
+Tapestry:      O(log^2 n)      O(log n)        O(log n)        (2^b - 1)(log 
n)/b 
+Kademlia:      O(log n)*       O(log n)        O(log n)        2(log n)
+Viceroy:       O(log n)        O(1)            O(log n)        10
+SWAN 1):       O(1)            O(1)            O(log^2 n)      r(b+2l+2s) (r=# 
of resurces provided, b=boot, s=short, l=long), typical link conf: 6+2*7+2*8=36 
+Flooding:      O(1)            O(1)            O(n)**          typical conf: 
5, depends on implementation              
+Social:                O(1)***         O(1)***         N/A***          can be 
1-10000 connections (aka social connections, connections are permament)
+Skip graphs 1): O(log n)       O(log n)        O(log n)        4r(log n) + 
(log n) (r=# of resurces provided)
+Symphony:      O(log^2 n)      O(log n)****    O(log n)        2k+2+f (k = 
long, 2 = node's neighbor, f = fault-tolerance links)
+Plaxton et al: not supported   O(log n)        O(log n)        2log n
 
 * = In Kademlia, there is no action required when nodes leaves the system
 
-** = Please see http://www.darkridge.com/~jpr5/doc/gnutella.html for details
+** = Number of messages can grow as fast as O(n^2)
 
 *** = From p2p-hackers mailinglist:
 
 **** = Can be also O(1). Additional space of 'space^2' can be used as a 
lookahed list for better performance
 
 1) = In these approaches, node is treated as 'named resource'; in this 
approach, *resources* self-organise (opposite to DHTs).
-E.g., in Skip graphs, a peer (i.e. computer) needs 2k(log n) space for k 
resources. SWAN requires O(1) space for neighbor links. 
+E.g., in Skip graphs, a peer (i.e. computer) needs 2k(log n) space for k 
resources. SWAN requires O(1) space.. 
 - - -
 
 > Btw, how well Alpine can scale (e.g. number of users) ? Do you have any 
 > "real-