A Scalable Content-Addressable Network
ACM SIGCOMM Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications (SIGCOMM), 2001 · paper · Computer science
Introduces the Content-Addressable Network (CAN), a distributed, hash-table-like infrastructure operating at Internet scale. Simulations demonstrate that it is scalable, fault-tolerant, self-organizing and low-latency.
Checked: PDF from web.stanford.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
2 findings
Substance Section 4: scaling the n=2^18 system "by another 2^10, reaching a system size of close to a billion nodes". 2^18 × 2^10 = 2^28 ≈ 268 million.
- p. 8 Section 4, extrapolation paragraph
system by another 2^10, reaching a system size of close to a billion
- p. 8 Section 4, extrapolation paragraph
scale the size of the system by another 2^10, reaching a system size of close to a billion nodes
- p. 8 Section 4, extrapolation paragraph
reaching a system size of close to a billion
Only the authors can say what is right here.
Judge's note: The paragraph continues from the knobs-on-full runs up to 2^18 nodes (p.8). Multiplying by 2^10 gives 2^28, about 0.27 billion, roughly a quarter of 'close to a billion'. Either the factor (about 2^12) or the stated size is off; only the authors can say which was intended.
Second check: another model agreed
Report a problem with this finding
Reference or label Section 4 item 2: "(without the landmark ordering feature from Section 3.7)". Landmark ordering is described in Section 3.6; Section 3.7 is More Uniform Partitioning.
- p. 8 Section 4, list item 2
(without the landmark ordering feature from Section 3.7)
- p. 6 Section 3.6 heading/body
Topologically-sensitive construction of the CAN overlay network
Judge's note: On p.6, Section 3.6 introduces landmark ordering and Section 3.7 is 'More Uniform Partitioning', which itself refers to 'the landmark ordering scheme from Section 3.6'. Table 4 has Uniform partitioning ON and Landmark ordering OFF for knobs-on-full. The pointer should be to 3.6.
Second check: another model agreed
Report a problem with this finding
15 minor (typos and the like; most checked by the judge only)
Wording Section 3.3 says RTT weighting "lowers the per-hop latency by between 24% and 40%", but the largest reduction in Table 1 is 38.6%.
- p. 5 Section 3.3, paragraph after Table 1 reference
lowers the per-hop latency by between 24% and 40%
- p. 6 Table 1
115.4
Judge's note: Table 1 (p.6) values computed. The lower bound of 24% is given precisely, but the upper bound of 40% rounds 38.6% up. The overstatement is small.
Second check: another model agreed
Report a problem with this finding
Wording It is unclear whether p counts all nodes in a zone or only the other peers. Table 4 gives p=0 for bare bones and Table 5 '# peers' 0, while Table 3 gives path length O(1/p) and Table 2 counts 'Number of nodes per zone' from 1.
- p. 8 Table 4, row p
p
- p. 9 Table 3, row 'number of peer nodes per zone', path length column
O(1/p)
- p. 6 Table 2 header
Number of nodes per zone
- p. 5 Section 3.4
MAXPEERS, which is the maximum number of allowable peers per zone
Only the authors can say what is right here.
Judge's note: Table 4 (p.8) gives p=0 and 4; Table 3 (p.9) gives O(1/p) and O(p); Table 2 (p.6) counts nodes per zone 1–4. Section 3.4 (p.5) uses both 'fewer than MAXPEERS peer nodes' and 'already has MAXPEERS nodes'. O(1/p) is undefined at p=0 under the Table 4 convention. This is a definitional ambiguity, not a data error.
Second check: another model agreed
Report a problem with this finding
Wording Section 3.6 points to "background load balancing techniques (as described in Appendix A) where an overloaded node hands off a portion of its space to a more lightly loaded one", but Appendix A describes zone reassignment to restore one zone per node after takeover.
- p. 6 Section 3.6, paragraph on uneven population
The use of background load balancing techniques (as described in Appendix A) where an overloaded node hands off a portion of its space
- p. 12 Appendix A
CAN MAINTENANCE: BACKGROUND ZONE REASSIGNMENT
Judge's note: Appendix A (p.12) gives a hand-off and merge procedure motivated by takeovers leaving a node with several zones. Load is not mentioned. The hand-off mechanism could be reused, so the pointer is loose rather than wrong.
Second check: another model agreed
Report a problem with this finding
Wording Knobs-on-full is described as "making full use of our added features (without the landmark ordering feature ...)", yet Table 4 sets r=1 and k=1, the same as bare bones.
- p. 8 Section 4, list item 2
a “knobs-on-full” CAN making full use of our added features
- p. 8 Table 4, rows r and k
Table 4: CAN parameters
Judge's note: Table 4 (p.8) shows multiple realities and multiple hash functions unused in knobs-on-full, but the text names only landmark ordering as excluded. This is a wording overstatement only.
Second check: another model agreed
Report a problem with this finding
Wording In Section 5.1, n is defined as the Plaxton label length ("a unique n bit label", w = n/l), and the next paragraph uses n as the number of nodes ("For a system with n nodes ... O(log n)").
- p. 9 Section 5.1, Plaxton description
every node is assigned a unique n bit label
- p. 10 Section 5.1, first line
For a system with n nodes, Plaxton’s algorithm routes in O(log n)
Judge's note: On p.9 the Plaxton description uses n for bits, and p.10 immediately reuses n for node count. Context resolves the meaning, but the notation clashes.
Second check: another model agreed
Report a problem with this finding
Typo Conference line has a doubled full stop: "San Diego, California, USA.."
- p. 1 Copyright block
San Diego, California, USA..
Judge's note: The crop of the p.1 copyright block shows 'USA..' with two full stops.
Second check: none (judge only)
Report a problem with this finding
Typo Section 2.3: "is smaller that its own zone volume" should read "smaller than".
- p. 3 Section 2.3, TAKEOVER paragraph
is smaller that its own zone volume
- p. 3 Section 2.3, TAKEOVER paragraph
is smaller that its own zone
Judge's note: The p.3 right column, TAKEOVER paragraph, reads 'smaller that its own zone' in the image.
Second check: none (judge only)
Report a problem with this finding
Typo Section 2.2: "are also transfered to the new node" is misspelt; it should be "transferred".
- p. 3 Section 2.2, Finding a Zone
are also transfered to the new node
Judge's note: The p.3 left column image shows 'transfered'.
Second check: none (judge only)
Report a problem with this finding
Typo Section 3.4: "Node B informs each of the nodes on it’s peer-list" uses the contraction 'it’s' where the possessive 'its' is meant.
- p. 5 Section 3.4, right column
Node B informs each of the nodes on it’s
- p. 5 Sec 3.4
each of the nodes on it’s
Judge's note: Confirmed in the p.5 right column image.
Second check: none (judge only)
Report a problem with this finding
Typo Section 4: "from 4.56 hops with 2^14 nodes to 5.0 with 2^18 hops". The last word should be 'nodes'.
- p. 8 Section 4, right column
to 5.0 with 2^18 hops
- p. 8 Section 4, scaling paragraph
to 5.0 with 2^18 hops)
- p. 8 Sec 4, scaling paragraph
to 5.0 with
Judge's note: The p.8 right column image reads '2^18 hops'. The parallel phrasing and the 2^14–2^18 node range show the system size is meant.
Second check: none (judge only)
Report a problem with this finding
Typo Table 3, 'size of data store' cell for peer nodes per zone, reads "replicated data store repli-cated: O(p)", repeating 'replicated'.
- p. 9 Table 3, row 'number of peer nodes per zone', column 'size of data store'
replicated data store repli- cated: O(p)
Judge's note: The rotated Table 3 on p.9 shows 'replicated data store repli- cated: O(p), partitioned data store: -'. The adjacent availability cell reads 'replicated data store: O(p)'.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [13] author list is printed as 'A. D. R. Marc Waldman and L. F. Cranor', which runs initials and a full name together and does not follow the 'Initials Surname' format of the other entries.
- p. 11 Reference [13]
A. D. R. Marc Waldman and L. F. Cranor
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that the intended authors are M. Waldman, A. D. Rubin and L. F. Cranor. The crop of p.11 confirms that the entry is printed exactly as quoted; it is not an extraction artefact. The format clashes with every other reference, but the correct author list cannot be fully recovered from the files.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [11] reads 'Proceedings of the Eight IEEE International Conference on Network Protocols'; the ordinal should be 'Eighth'.
- p. 11 Reference [11]
Proceedings of the Eight IEEE International Conference
Judge's note: The crop of p.11 shows 'Eight' printed in the italic venue name. This is an ordinal misspelling with an obvious fix.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [21] lists the author 'N. Borishov'; the name is probably 'N. Borisov'.
- p. 11 References [21]
N. Borishov
Only the authors can say what is right here.
Judge's note: Rests on outside knowledge: that the co-author of the 1999 Berkeley technical report is Nikita Borisov. The crop of p.11 confirms the printed spelling 'Borishov'. The files contain nothing to check it against, so only the authors can confirm.
Second check: none (judge only)
Report a problem with this finding
Typo Appendix A defines a binary 'partition tree' but then calls the current zones '(the leaves of the deletion tree)' and later writes 'the dissection tree is well balanced'; neither term is defined.
- p. 12 Appendix A
(the leaves of the deletion tree)
- p. 12 Appendix A, last paragraph
the dissection tree is well balanced
- p. 12 Appendix A
the leaves of the deletion tree
Judge's note: Checked the crops of p.12. The tree is introduced as the 'partition tree', and the same paragraph goes on to say 'operations on the partition tree'. 'Deletion tree' is clearly a stray term for the same structure, since its leaves are the current zones. 'Dissection tree' is closer to the paper's earlier wording ('a dissection of the coordinate space') but is still an undefined third name. The meaning can be recovered, so this is a cosmetic terminology fix: use 'partition tree' throughout.
Second check: none (judge only)