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

[Hermanni Hyytiälä]

On Tue, 2003-06-17 at 13:54, Tuomas Lukka wrote:
> 
> > > 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?

I don't understand your "n-1 \approx n" syntax completely. Does that
mean that "n is an approximation, and...", or "Now, we replace this with
this, and...", ... ?

> 
> > 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?

Yes, right. But in this case we can assume that this is an ideal network
that suits for our purposes and simplifies formula, right? In practice
of course, it's not guaranteed.



-Hermanni