[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/20 02:39:12

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

Log message:
        Summary table updates

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.20 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.21
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.20      Mon Jan 
20 02:20:20 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Mon Jan 20 
02:39:12 2003
@@ -109,7 +109,7 @@
 (in DHTs this is a open problem)
 +There are not hotspots in skip graphs (query/routing hotsports)
 -not network/geographical locality
--for us purposes, Skip Graps could be used (sensible) only for block IDs, not 
for URNs: in Skip Graps, there have to be total order for data elements --> for 
URNs, there cannot be a total order
+-for our purposes, Skip Graps could be used (sensible) only for block IDs, not 
for URNs: in Skip Graps, there have to be total order for data elements --> for 
URNs, there cannot be a total order
 -for range queries, we would have to use local sensitive hashing, *if* we want 
fetch blocks like 'next block = i + 1'. SHA-1 is a (secure) random hash of 
content (it won't help for us in this case) 
 
 
@@ -147,17 +147,20 @@
 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:  O(1)            O(1)            O(log^2 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:    O(log n)       O(log n)        O(log n)
+Skip graphs 1): O(log n)       O(log n)        O(log 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
 
 *** = From p2p-hackers mailinglist:
+
+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. 
 - - -
 
 > Btw, how well Alpine can scale (e.g. number of users) ? Do you have any 
 > "real-