[chord] How to infer the O(log N) in the Chord paper?
ISO
ISO2000 at citiz.net
Thu Apr 29 20:32:55 EDT 2004
Hi,all
I just have read the technical report on Chord,
however, I am puzzled at the result of O(log N).
That is, at the page 8, saying "In this case, the
load on a node may exceed the average by (at most)
an O(logN) factor with high probability (or in our
case, based on standard hardness assumptions)." But
how can we infer the O(log N) factor based on the
standard hardness assumptions?
Also, I am puzzled at the proof of the theorem 4.2,
at page 11, which says that "In fact, as discussed
above, we assume that node and key identifiers are
random. In this case, the number of forwardings
necessary will be O(logN) with high probability. "
How to affirm being O(log N)?
Can you give me some more detailed explanation?
Thanks!
Jie
-------------- next part --------------
An HTML attachment was scrubbed...
URL: https://amsterdam.lcs.mit.edu/pipermail/chord/attachments/20040429/1bf90c4b/attachment.htm
More information about the chord
mailing list