Re: [Gzz] hemppah's research problems document

[hemppah]

Quoting "B. Fallenstein" <address@hidden>:

> 
> Hi Hermanni,
> 
> we seem to be miscommunicating again and again... sorry. *sigh* Please, 
> be as explicit as possible when answering, to avoid misunderstandings... 
>   :-/

Yes, I will try. The fact is, I have no experience about *real disccusions* in
the mailing lists. My experience is about chatting, and therefore my statements
are quite outbounded sometimes. I will try make my statements better...

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

> 
> > Indeed,
> > authors suggest that setting as d = log n, CAN has O(log n) neighbors and
> O(log
> > n) pathlengths like other DHT algorithms.
> 
> So? That still means that *some* DHT algorithms perform as you said, 
> *but not all* (CAN with say, 3 dimensions).

Again, I cited the d = log n only because in "real life" (and as the authors
suggest), setting d = log n is very recommended for better efficiency. But, I do
agree with your statment :).


> 
> >>>-SWNs require O(log^2 n) hops to reach arbitrary destinations, assuming
> >>>(*only and only if* !!!) that 
> >>>links between nodes are constructed in the way that they are uniformly
> >>>distributed over all distances 
> >>>in the network (Kleinberg)
> >>
> >>"only and only if"? :)
> > 
> > Yes! There have to be *very* careful (aka "clever") when constructing
> links
> > between nodes in SWNs. See Jon Kleinberg's works for details (google jon
> kleinberg)
> 
> "only and only if" is still not a meaningful English expression, AFAIK ;-)

Yes, I agree. Here are the two requirements:

Req. 1:
The short-range links must be such that for all nodes n and m, where n != m, n
has a short-range link to a node l, so that distance(l, m) < distance(n, m).

Notice: The length of the link from node n to node m is distance(n, m)

Req. 2:
The long-range links must be such that for all Long-range links are nearly
uniformly distributed over all 'distance scales'. 

Notice: There *is* a more formal specification about req. 2, but I won't give it
right here, because it quite mathematical (and therefore it makes no sense to
present it here with these characters).

And, if these requirements are met, SWN network can locate any data in O(log^2
n) hops (Kleinberg and e.g. simulations in SWAN)

Okay ?


> 
> >>>-Example systems: SWAN, Freenet
> >>
> >>Freenet? Freenet definitely does not have the properties of storing 
> >>mappings on your machine-- in Freenet, *everything* is distributed 
> >>through the network.
> > 
> > 
> > Umm..perhaps I should be more specific. Basically I have categorized
> these
> > systems based on the routing mechanism. I should, however, update the
> section
> > names for better clearance.
> 
> No, you should make clear that the characterizations you list do not 
> apply to all examples you give.

Yes, I will try to do better. As said, this document is pre-draft and far from
complete :).


> >>
> >>My problem: If it's 1), this is just another type of DHT. If it's 2), 
> >>it's about as attractive as flooding broadcast networks, because it 
> >>simply doesn't scale.
> > 
> > I think the first approach is more close ("somekind of DHT")...
> 
> Sorry if this sounds harsh :-( but your work is of no use to me as long 
> as you don't clearly explain the algorithms you're talking about. I said 
> that I see only two interpretations of what you said: DHT or 
> one-node-per-block. I see no others, so if you say one of these is 
> "close," but not quite there, I haven't been helped at all. Please, 
> either explain how this works, or say that you can't and why.
> 
> (In case you don't really know how it works: That's not a problem. But 
> then, please *say* so instead of making asserions about this sysatem and 
> its properties...)
> 
> Sorry, but this is really important for your work to be useful to us 
> others in the group...

This sounds no harsh at all, I fully understand your frustration :-).

I prefer not to explain any details here. It would better if you could have the
whole article for reading. I'll ask the authors if they allow be to distribute
SWAN articles within our research group.

Okay ?


> >>- "...can be performed locally"? It's like loading blocks: If you don't 
> >>have the data, you must request it from the network.
> >>- Why logarithmic time? Locally, we can use a hashtable -> O(1)?
> > 
> > Also, look above :). Ok, to be more specific: worste case is locarithmic
> time,
> > usually constant time.
> 
> Sorry, I understand neither of these hints. Could you reply to my 
> questions directly-- what do you mean by "can be performed locally," and 
> what do you mean by 'logarithmic time'? (If you're giving 'logarithmic 
> time' as the worst-case performance of hashtables, I think that should 
> be 'linear time'?)

"can be performed locally" = work done in node's local data structures

"logarithmic time" = fast enough

Again, this *assumption* is based on IRC discussion between Tuomas and I. Tuomas
said, that you node's local work (searching etc.) can be done "fast enough"
(e.g. logarhitmic, constant etc). 

I use these terms by turns. Sorry for that.

> 
> >>>2.2.4. Open questions:
> >>>-in this case, is it sensible to maintain two different key-value
> mappings
> >>
> >>key-value based systems (DHT, SWN) ?
> >>
> >>>   -one fore block IDs
> >>>   -one for urn-5 names, which are associated with block IDs
> >>>   -is this approach too difficult to maintain ?
> >>
> >>Why would one want to? I don't see any benefits.
> > 
> > This is based on my preasumption below.
> 
> Which one?

Sorry, preasumption *above*:

"I may have understood this all wrong, but if we want all blocks associated with
a specific urn-5, we have to check all blocks (since from this point of view,
urn-5 and block IDs are independent from each other: urn-5 names has no
information about the blocks which may associated with the specific urn -5 ??) 
? "

> 
>  > If we know all the block's associated
> > with a given urn-5, we can find the block(s) more efficiently.
> 
> Well, duh. But your question was (or I understood it as) whether it 
> makes sense to maintain *two different* key-value based systems for 
> block IDs and urn-5 names. I don't see why you would want to-- you can 
> store both mappings in a single DHT (which is probably more efficient 
> than having two parallel DHTs, and also easier to maintain).

Yes, it could be more efficient not to maintain two different key-value.

Do you know if any analysis of these kinds of systems exists ? Initial reaction
would be that, there would be much more overhead/maintenance problems in these
systems, if nodes leave and join constantly (Am I wrong ?).

> 
> >>>-is there possibility, in the specific urn-5 name, to maintain
> >>>information
> >>>about most recent block's ID for better search performance (or moreover,
> >>>tree based structure for all blocks for specific urn-5 name) ?
> >>
> >>No. You create the urn-5 *before* you create any of the blocks, so you 
> >>cannot make it depend on the blocks (that's why we can't use 
> >>cryptographical hashes).
> > 
> > Heh...here's the answer for my two answers above :).
> 
> What do you mean?

I meant that you answered by question which I posed earlier (by saying urn-5 are
created before of blocks).

Okay ?


-Hermanni




-------------------------------------------------
This mail sent through IMP: http://horde.org/imp/