[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/19 04:06:32

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

Log message:
        system in flux: half life phenomenon

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

Patches:
Index: gzz/Documentation/misc/hemppah-progradu/research_problems
diff -u gzz/Documentation/misc/hemppah-progradu/research_problems:1.10 
gzz/Documentation/misc/hemppah-progradu/research_problems:1.11
--- gzz/Documentation/misc/hemppah-progradu/research_problems:1.10      Wed Dec 
18 09:24:48 2002
+++ gzz/Documentation/misc/hemppah-progradu/research_problems   Thu Dec 19 
04:06:32 2002
@@ -258,6 +258,17 @@
        -coping with system in flux
                -large system may never achieve a ideal state
                -no overwhelming theory for handling system in flux
+               -normally, in DHTs/SWNs lookup takes log (n) hops, *if* system 
is stable, but system is never stable
+               -the goal is to create theoremns of the type:
+               1. in the almost-ideal state, log(n)
+               2. system maintains almost-ideal state as nodes join and fail
+               -Half life phenomenon: 
+                       -doubling time: time for n joins
+                       -halfing time: time for n/2 old nodes to fail
+                       -half life: MIN(doubling time, halfing time)
+               -applying half life:
+                       -for any node n in network:
+                       -if n wishes to stay connected whp, then on average, u 
must be notified about log(n) new per half life                  
        -robustness with untrusted participants
                -data authentication
                -self-certifying pathnames
@@ -296,10 +307,10 @@
                        -solution: (partial solution) the defence against this 
would be standard authentication techique, such as digital signatures. However, 
                                   there are no working implementation for this 
yet (digital signatures are expensive currently)
                
--summary: 
+-security summary: 
        -problem: attacker denies service, attacker return incorrect data and 
attacker denies data exists:
        -solution: redundancy (replication, caching)
-       -problem: sybil attack (attacker creates multiple identities and foils 
the redundancy
+       -problem: sybil attack (attacker creates multiple identities and foils 
the redundancy)
        -solution: need a way to control creation of node IDs (ID = 
SHA-1(ip-address), challange node verify its ID)