[Gzz-commits] storm/doc/pegboard/storm_gisp_simulation--hempp...

[Hermanni Hyytiälä]

CVSROOT:        /cvsroot/storm
Module name:    storm
Changes by:     Hermanni Hyytiälä <address@hidden>      03/06/04 07:12:53

Modified files:
        doc/pegboard/storm_gisp_simulation--hemppah: peg.rst 

Log message:
        gisp protocol

CVSWeb URLs:
http://savannah.gnu.org/cgi-bin/viewcvs/storm/storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst.diff?tr1=1.6&tr2=1.7&r1=text&r2=text

Patches:
Index: storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst
diff -u storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst:1.6 
storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst:1.7
--- storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst:1.6       Wed Jun 
 4 04:38:35 2003
+++ storm/doc/pegboard/storm_gisp_simulation--hemppah/peg.rst   Wed Jun  4 
07:12:52 2003
@@ -5,8 +5,8 @@
 
 :Authors:  Hermanni Hyytiälä
 :Date-Created: 2003-06-02
-:Last-Modified: $Date: 2003/06/04 08:38:35 $
-:Revision: $Revision: 1.6 $
+:Last-Modified: $Date: 2003/06/04 11:12:52 $
+:Revision: $Revision: 1.7 $
 :Status:   Incomplete
 
 .. :Stakeholders:
@@ -58,20 +58,46 @@
     Why GISP? Why are we using it versus some other systems?
     What properties does it share with others, to such a degree
     that its performance might be deduced from theirs?
+
+    RESOLVED:
+    
+    Why GISP ? Why are we using it versus some other systems?
+    
+    1) According to Benja, "it's written in Java" :)
+    2) Aasy implementation (and it's implemented)
+    3) (belief that) GISP is a Kademlia implementation (which
+     is not true - only distance function is similar)
+     
+    There is also a Python implemenation of Kademlia called
+    Kashmir_.
+     
+    What properties does it share with others, to such a degree
+    that its performance might be deduced from theirs?
     
-    -because "it's written in Java"
-    -Kashmir - a Python implemenation of pure Kademlia
-    -with Kademlia: XOR-metric
-    -with Chord: routing table (more space for cache)
+    GISP's routing table is based on Chord's routing 
+    table - O(log^2 n) messages are required to join/leave 
+    operations and O(log n) lookup efficiency (according to 
+    original Chord publication). GISP extends Chord's routing
+    table to have more space for cached data (peer information)    
+       
 
 ISSUE:
         
     What experiments / simulations / methods are used in the literature?
     
-    -rather static simulations
+    RESOLVED:
+    
+    -very early (theoretical) experiments
+     -limited amount of uncontrolled (real life), great amount of
+     controlled (simulation environment)
+    -simulations have been rather static and are often favored a 
+     proposed algorithm
     -not much real life experiments
-    -simulations
-    -formal analyses
+     -somewhat controlled experiments
+     -very fast connections between peers
+    -some form of formal analyses ("proofs") are used with, 
+     e.g., Chord and Kademlia
+    -number of peers used in simulations: from 2^7 to 2^20 
     
 Plan
 ====
@@ -81,31 +107,38 @@
 if necessary, we program (rather short) test cases which will test 
 the GISP/Storm P2P properties, as discussed in this document. Finally, we will 
 collect and analyse test cases' information and publish any interesting 
-discoveries. 
+discoveries.
+ 
 
 The GISP protocol
 =================
 
-- "GISP intends leverage those (DHT) algoritms and make a practical protocol."
-- *distance function* is based on XOR-metric (Kademlia uses XOR)
-- protocol (most recent) talks about XOR-metric, publication
-  numerical metric
-- lacks of Kademlia's binary-tree abstraction (routing table) -the benefits 
-  of Kademlia's  lookup properties are not available
-- uses Chord_'s extended routing table expect more space is used for caching 
-  (Log^2 messages): asymmetric (requires stabilization protocol like Chord)
-  and lookup process is unidirectional (a virtual ring)
-  -Chord's routing table is rigid compared to Kademlia's (well known issue)  
-- replicates in a same way as Kademlia ?
-- no concurrent RPCs during lookup -- no free of choice during 
-  lookups ? 
-- does GISP have the property of Kademlia: leaving peer costs nothing ?
-   - no, since GISP's routing table is based on Chord's routing table
-- supports "peer strength" for peer heteregeneity
-- nothing mentioned about the overlay topology -- however, routing table
-  is based on Chord's routing table --> toplogy resembles Chord's virtual
-  ring
+According to Daishi Kato, the author of GISP, GISP ''...intends leverage 
+those (DHT) algoritms and make a practical protocol.''. GISP's distance 
+function is based on the XOR-metric, which is similar to Kademlia's XOR-metric 
+(unsigned integer of XOR). The GISP protocol specification paper describes the 
+XOR-metric but the original GISP publication describes only numerical 
+metric (which is little confusing since Chord_ uses numerical distance
+metric).
+
+GISP extends Chord's routing table to have more peer information as a cache.
+Thus, log^2 messages are required to join/leave operations (according to the
+original Chord publication). Additionally, Chord's routing table is asymmetric 
+(requires stabilization protocol) and lookup process is unidirectional 
+(in a virtual overlay ring). Original Kademlia publication states that 
+Chord's routing table is rigid compared to Kademlia's routing table.
+
+Since GISP lacks of Kademlia's binary-tree-like abstraction of the routing 
+table, it is evident that the benefits of Kademlia's lookup properties (over 
+other DHTs) are not available in the GISP protocol, e.g., no concurrent and
+asynchronous lookups (no free of choice) and when a peer leaves the system
+no messages are required.
+
+Original GISP publication describes "peer strength" as a measure for peer 
+heteregeneity but do not describe what properties are used and how this
+value is calculated.
 
+For network communication the GISP protocol uses XML-RPC.
 
 Research problems
 =================
@@ -120,6 +153,9 @@
 
 - GISP does not use Kademlia's binary-tree abstraction - does it have 
influences 
   and if it does, what are the influences ? 
+  
+- How much better/worse pure Kademlia implementation (e.g. Kashmir) is over 
the GISP 
+  protocol if face performance and fault-tolerance ?
          
 - How well GISP is able to perform in adverse conditions, e.g., a
   network partition occurs ?
@@ -203,3 +239,4 @@
 .. _GISP: http://gisp.jxta.org
 .. _Kademlia: http://kademlia.scs.cs.nyu.edu
 .. _Chord: http://www.pdos.lcs.mit.edu/chord/
+.. _Kahsmir: http://khashmir.sourceforge.net/