[chord] Some questions about Chord

[Yu Yun-Shuai]

Dear authors,
    I am a phd student in NCKU, Taiwan. I read your paper "Chord: A Scalable 
Peertopeer Lookup Service for Internet Applications" recently. It taught and 
edified me a lot. I also shared it with my friends. We thought it is a very 
good paper.

    But we are confused with one theorem. Could you explain it in detail?. 
Below is the theorem:

THEOREM 3. With high probability, any node joining or leaving an N-node Chord 
network will use O(log^2 N) messages to re-establish the Chord routing 
invariants and finger tables.

    In the Chord paper published in SIGCOMM¡¦01, it says the theorem is 
proved in the technical report [21]. I found the report on the website 
http://www.pdos.lcs.mit.edu/chord/papers/ , and download another document: 
chord.pdf.

    In the page 15 of chord.pdf, the second paragraph says (n-p) = O(2^m
(logN)/N). We have no idea about this statement. Could you give us more 
information about this paragraph?

    In the page 12 of chord.pdf, the third paragraph says We show in Section 
6 that the number of nodes that need to be updated when a node joins the 
network is only O(logN), on the average, and with a very high probability is 
at most O(log^2 N) , where N is the total number of nodes in the network. Why 
do you use "node" here but "messages" in the THEOREM 3?

    We thank for your kind attention on our inquiry and look forward to your 
prompt reply.

Best Regards,
Yu Yun-Shuai
             2004/04/28