[chord] How to infer the O(log N) in the Chord paper?

ISO ISO2000 at citiz.net
Thu Apr 29 20:13:31 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?

   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/93b0a197/attachment.htm


More information about the chord mailing list