Re: [Gzz] hemppah's research problems document

[Tuomas Lukka]

> > address@hidden wrote:
> > >>>-DHTs require O(log n) hops to reach arbitrary destinations, assuming
> > that
> > >>
> > >>each node maintains 
> > >>
> > >>>information about O(log n) nodes
> > >>
> > >>This is not true. *Some* DHT routing algorithms require O(log n) nodes 
> > >>to be stored, but CAN or a small-world assumption-based routing 
> > >>algorithm only require O(1) neighbours (where CAN routing takes square 
> > >>root time). You say that yourself, below.
> > > 
> > > 
> > > For CAN, though, for only *oneÄ dimension is a "special" case.  For CAN,
> > when
> > > there is a only one dimesion, CAN performance is far for other DHTs.
> > 
> > I don't understand these two sentences...
> 
> To put simply (this is what I meant): AFAIK, if you use CAN with 1 dimension 
> the
> performance of CAN is far from reqular DHTs. Understood and agree ?

1 is not the same as O(1) !!

        Tuomas