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

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/gzz
Module name:    gzz
Changes by:     Hermanni Hyytiälä <address@hidden>      02/12/17 03:27:50

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

Log message:
        Updates to summary table

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.3 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.4
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.3       Mon Dec 
16 09:14:48 2002
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Tue Dec 17 
03:27:50 2002
@@ -21,7 +21,7 @@
 -Of couse, there is the possibility to route in constant times, but it 
requires that *each** node
 maintains information about all the nodes in the network. Therefore , 
practically, this method 
 impossible
--Example systems: Chord, CAN, Kademlia, Pastry, Tapestry
+-Example systems: Chord, CAN, Kademlia, Pastry, Tapestry, Viceroy
 
 *Update*
 -Viceroy system achieves O(log n) hops with only O(1) neighbors
@@ -75,24 +75,24 @@
 This summary table is far from complete (and from total truth)
 
                Insert/Delete   Space           Search
-Chord:                 O(log^2 n)      O(nlog n)       O(log n)
-CAN:           O(r)            O(nr)           O((r/4)n^(1/r)), where r is the 
number of dimensions used in a virtual space
-Pastry:        O(log^2 n)      O(nlog n)       O(log n)
-Tapestry:      O(log^2 n)      O(nlog n)       O(log n)
-Kademlia:      N/A             O(log n)        O(log n)
-Viceroy:       N/A             7               O(log n)
-Small Worlds:  N/A             O(1)            O(log^2 n)
+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:  O(1)            O(1)            O(log^2 n)
 Flooding:      N/A             O(1)            "high"
 Hybrid:                N/A             N/A             N/A
 Social:                N/A             O(1)            N/A
 
-*I will try fill in N/As as quickly as possible!*
+* = In Kademlia, there is no action required when nodes leaves the system
 
 Insert/Delete: 
 Number of messages when a node joins or leaves the network.
 
 Space: 
-Total amount of space required in a system for routing tables
+Space required for a node's neighbors
 
 Search: 
 Number of messages when an object lookup is performed