Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications
Proceedings of the 2001 conference on Applications, technologies, architectures, and protocols for computer communications, 2001 · paper · Computer science
Presents Chord, a distributed lookup protocol that maps a key onto a node in peer-to-peer systems. Theory, simulations and experiments show communication cost and per-node state grow logarithmically with the number of nodes.
Checked: PDF from pdos.csail.mit.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
4 findings
Substance In Figure 5(b), node 0's first finger row reads "1 [1,2) 0" (drawn in black as changed), but with nodes {0,3,6} remaining, successor(1) is 3.
- p. 6 Figure 5(b), finger table of node 0, first row
1 [1,2) 0
Judge's note: The zoomed crop shows node 0's table in (b) as: 1 [1,2) 0 in black, 2 [2,4) 3 in gray, 4 [4,0) 6 in gray. With remaining nodes 0, 3 and 6 (and node 3 holding key 1), the successor of identifier 1 is node 3, not node 0. Node 0 cannot be its own first finger while other nodes exist.
Second check: another model agreed
Report a problem with this finding
Substance Section 6.2 reads "we would like the distribution of keys to nodes to be tight around N/K"; with N nodes and K keys, the mean number of keys per node is K/N.
- p. 8 Section 6.2, first paragraph
like the distribution of keys to nodes to be tight around N/K
Judge's note: The page 8 image shows "N/K" in Section 6.2. In the same paragraph, N is the number of nodes and K the number of keys. The experiments that follow (10^4 nodes, 5x10^5 keys, mean 50) use K/N, so the printed ratio is the reciprocal.
Second check: another model agreed
Report a problem with this finding
Substance Section 6.2 reads "The maximum number of nodes stored by any node in this case is 457"; the quantity is keys per node.
- p. 8 Section 6.2
number of nodes stored by any node in this case is 457
- p. 8 Section 6.2, discussion of Figure 8(b)
The maximum number of nodes stored by any node in this case is 457
Judge's note: Page 8, Section 6.2: the sentence is about the PDF of keys per node in Figure 8(b), with 5x10^5 keys on 10^4 nodes. 457 is 9.1 times the mean of 50 keys, so 'nodes' should read 'keys'.
Second check: another model agreed
Report a problem with this finding
Reference or label The Figure 5 caption reads "(b) Finger tables and key locations after node 3 leaves.", but panel (b) shows node 1 departing.
- p. 6 Figure 5 caption
(b) Finger tables and key locations after node 3 leaves.
Judge's note: In panel (b) the remaining (green) nodes with finger tables are 0, 3 and 6. Node 1 is drawn as a plain dot with no table. Node 3 now holds keys 1 and 2, with key 1 drawn in black, i.e. changed. That is only consistent with node 1 leaving, so the caption names the wrong node. No text elsewhere in the paper refers to panel (b).
Second check: another model agreed
Report a problem with this finding
8 minor (typos and the like; most checked by the judge only)
Wording Theorems 7 and 8 assume "a successor list of length r = O(log N)", yet the guarantee needs r at least about log N ("2^-r = 1/N").
- p. 8 Theorem 7 / Theorem 8
successor list of length r = O(log N)
- p. 8 intuition paragraph
successors all fail with probability 2^{-r} = 1/N
Only the authors can say what is right here.
Judge's note: Page 8: both theorem statements use r = O(log N). An upper bound alone allows r = 1, and then the probability that all successors fail is 1/2, not 1/N, so a lower bound (Omega or Theta) is what the argument requires. The intuition paragraph takes r = log N. This is very likely the common loose use of O for 'order log N', with the proof deferred to the technical report [21]. The stated results stand under the intended reading.
Second check: another model agreed
Report a problem with this finding
Typo Missing word: "Only one piece information per node need be correct" should read "one piece of information".
- p. 1 Introduction
Only one piece information per node need
- p. 1 Introduction, paragraph 4
Only one piece information per node need be correct
Judge's note: Page 1 image, Introduction right column, shows the wording as quoted. 'of' is missing.
Second check: none (judge only)
Report a problem with this finding
Typo Missing word: "queries make a logarithmic number hops" should read "a logarithmic number of hops".
- p. 2 Section 2, Plaxton paragraph
a logarithmic number hops
Judge's note: Page 2 image, Plaxton paragraph in Section 2, shows the wording as quoted.
Second check: none (judge only)
Report a problem with this finding
Typo Misspelling: "the algorithm always makes progress towards the precedessor of id" should read "predecessor".
- p. 4 Section 4.3
progress towards the precedessor
- p. 4 Section 4.3, find_predecessor discussion
towards the precedessor
- p. 4
Thus the algorithm always makes progress towards the precedessor
Judge's note: Page 4 image, Section 4.3 right column, shows 'precedessor'.
Second check: none (judge only)
Report a problem with this finding
Typo Section 6.3 reads "instead, we move on the the i-2nd bit"; this should be 'move on to the'.
- p. 9 Section 6.3
we move on the the
- p. 9
followed—instead, we move on the the bit. In general, th
Judge's note: The crop of page 9, right column of Section 6.3, shows "move on the the" as printed. It is not a line-break artefact.
Second check: code check
Report a problem with this finding
Typo Reference [2] reads "AND TANENBAUM., A.", with a stray period after the surname.
- p. 11 Reference [2]
AND TANENBAUM., A.
Judge's note: The crop of page 11 confirms the period between TANENBAUM and the comma. All other entries use the form SURNAME, I.
Second check: none (judge only)
Report a problem with this finding
Typo The Conclusion reads "solves this challenging problem in decentralized manner"; the article 'a' is missing.
- p. 11 Section 8 Conclusion
challenging problem in decentralized manner
- p. 11 Section 8
in decentralized manner
Judge's note: The crop of page 11, Section 8, confirms the wording as printed.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [12] reads "Proceeedings of the Ninth international Conference"; 'Proceedings' is misspelled.
- p. 12 Reference [12]
Proceeedings of the Ninth international Conference
Judge's note: The crop of page 12, reference [12], shows the triple 'e' in "Proceeedings".
Second check: none (judge only)