[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/16 06:51:40

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

Log message:
        Skip graphs: the best solution so far to our needs

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.14 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.15
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.14      Wed Jan 
 8 06:31:42 2003
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Thu Jan 16 
06:51:40 2003
@@ -96,7 +96,24 @@
 
 -Example systems: Alpine Network
 
-1.6. Summary
+
+1.6. Skip Graphs (based on skip lists)
++fast routing (aka searching)
++scalable
++little network traffic
++possibly, the best solution for our needs
++support *data* locality, opposite to DHTs where data is spread out evenly, 
destroying locality. In skip graphs, hashing is not requires, only *keys* 
matters (which we already have)
++support for partial repair mechanism/self-stabilization (DHTs lack of repair 
mechanism/self-stabilization)
++the most robust algorithm up to date, tolerance of adversial faults (DHTs 
support only of random faults)
++adaptive: doesn't need to know keyspace size before hand, instead of many 
DHTs, which require a priori knowledge about the size of the system or its 
keyspace
++support for range queries, e.g. natural for version control: 'find latest 
news from yesterday', 'find largest key < news:12/12/2002', 'find all related 
objects nearby'
+(in DHTs this is a open problem)
+-not network/geographical locality
+
+See summary table for performance details
+  
+
+1.7. Summary
 
 This summary table is far from complete (and from total truth)
 
@@ -111,6 +128,7 @@
 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)
 
 * = In Kademlia, there is no action required when nodes leaves the system