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

[Tuomas Lukka]

On Tue, Jun 17, 2003 at 01:43:32PM +0300, Hermanni Hyytiälä wrote:
> > >    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".

Umm, I wasn't clear.

If you use path length = O(log n)

then you're already making a large approximation, and assuming n is fairly
large.

In that case, 

        n-1 \approx n 

will hold and allows you to simplify your formulas nicely.

Ok?

> 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".

This is not guaranteed for any n queries, right?

> 3. "Repeat step 2. for all n nodes".
> 
> But I'm not sure if this is right thinking or not...

Sounds right but your presentation above is bizarre. Better use programmatic
notation: 

For all nodes n:

        do foo...

or something like it. Don't repeat afterwards without saying before that
youre *going* to repeat.

        Tuomas