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

[Tuomas Lukka]

On Tue, Jun 17, 2003 at 02:37:10PM +0300, Hermanni Hyytiälä wrote:
> 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...", ... ?

\approx is the wiggly equals sign in LaTeX.

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

Even in an ideal network, if you send n queries, you can't expect 
the targets to be on different hosts.

        Tuomas