Re: [Gzz] Re: [Gzz-commits] storm/doc/pegboard/attacking_gisp--hemppah peg.rst

[Hermanni Hyytiälä]

On Tue, 2003-06-17 at 13:02, Tuomas Lukka wrote:
> On Tue, Jun 17, 2003 at 02:57:13AM -0400, Hermanni Hyytiälä wrote:
> > CVSROOT:    /cvsroot/storm
> > Module name:        storm
> > Branch:     
> > Changes by: Hermanni Hyytiälä <address@hidden>      03/06/17 02:57:13
> > 
> > Modified files:
> >     doc/pegboard/attacking_gisp--hemppah: peg.rst 
> > 
> > Log message:
> >     fix
> > 
> > CVSWeb URLs:
> > http://savannah.gnu.org/cgi-bin/viewcvs/storm/storm/doc/pegboard/attacking_gisp--hemppah/peg.rst.diff?tr1=1.37&tr2=1.38&r1=text&r2=text
> > 
> > Patches:
> > Index: storm/doc/pegboard/attacking_gisp--hemppah/peg.rst
> > diff -u storm/doc/pegboard/attacking_gisp--hemppah/peg.rst:1.37 
> > storm/doc/pegboard/attacking_gisp--hemppah/peg.rst:1.38
> > --- storm/doc/pegboard/attacking_gisp--hemppah/peg.rst:1.37 Mon Jun 16 
> > 07:47:36 2003
> > +++ storm/doc/pegboard/attacking_gisp--hemppah/peg.rst      Tue Jun 17 
> > 02:57:13 2003
> > @@ -4,8 +4,8 @@
> >  
> >  :Authors:  Hermanni Hyytiälä
> >  :Date-Created: 2003-06-05
> > -:Last-Modified: $Date: 2003/06/16 11:47:36 $
> > -:Revision: $Revision: 1.37 $
> > +:Last-Modified: $Date: 2003/06/17 06:57:13 $
> > +:Revision: $Revision: 1.38 $
> >  :Status:   Incomplete
> >  
> >  .. :Stakeholders:
> > @@ -279,11 +279,11 @@
> >    fail.  
> >  
> >    n peers, O(log n) path length, all peers perform n lookups. Then the 
> > total
> > -  number of packets is (n-1)((n-1)(log n))
> > +  number of packets is n((n-1)(log n))
> >    
> >    n peers where fraction f are hostile, O(log n) path length, all peers 
> >    perform n lookups. Then the total number of lost packets is 
> > -  [f^((log n)-1)]*[(n-1)((n-1)(log n))]
> > +  [f^((log n)-1)]*[n((n-1)(log n))]
> >    
> Where are the sources / derivations for the formulas?

No sources, I derived those formulas myself, except that "f^((log n)-1)"
(i.e., "probability of routing wrong") is derived from the "probability
of routing successfully" formula: (1-f)^h-1. 

And the formula is an estimation (have to change the word in the PEG").

> 
> If you're using O(log n) for the path length, then you definitely
> should not let "n-1" enter the formulas anywhere...

Hm, "n-1" is in the formula since when a node queries the network, which
has n nodes, no network messages are required to query "my local data".

The idea behind the derivation is roughly:

1. "In a n node network, average lookup length is O(log n)".
2. "A node says: I will create (number of) n queries so that each query
will reach other node in the network. In the end, for each node in the
network, one query has reached the node".
3. "Repeat step 2. for all n nodes".

But I'm not sure if this is right thinking or not...


-Hermanni