Kademlia: A Peer-to-peer Information System Based on the XOR Metric
Lecture notes in computer science, 2002 · paper · Computer science
Describes Kademlia, a peer-to-peer key-value storage and lookup system that uses an XOR-based distance measure. The authors claim provable consistency and performance in fault-prone environments, with parallel asynchronous queries that tolerate node failures.
Checked: PDF from scs.stanford.edu, fetched 4 Oct 2026. Page numbers are those of that PDF.
0 findings
None that passed a second check.
13 minor (typos and the like; most checked by the judge only)
Wording Section 3: "the lookup procedure will find a node half as close (or rather whose distance is one bit shorter)"; read literally, "half as close" means twice as far, the opposite of the intended halving of distance ("half as far" in the Introduction).
- p. 4 Section 3, lookup argument
will find a node half as close (or rather whose distance is one bit shorter)
- p. 1 Introduction, last paragraph
half as far from the target ID
Judge's note: Page 4 crop: the parenthetical and the later "will not decrease the distance by half" show that halving the distance is intended. The wording as printed says the reverse. It is a wording slip whose meaning can be recovered from context.
Second check: another model agreed
Report a problem with this finding
Wording Section 3 defines "the depth, h, of a node" and "node y's bucket height in node x", then claims "the height of a any given node will be within a constant of log n"; "height" of a single node is never defined (depth appears to be meant).
- p. 4 Section 3, definitions
Define the depth, h, of a
- p. 4 Section 3, definitions
the height of a any given node will be within a constant of log n
- p. 4 Section 3, definitions
the height of a any given node will be within a
Judge's note: Page 4 (crop C006-a, same passage): depth is defined as 160 − i and bucket height is defined for a pair of nodes. The log n claim is then made about the "height" of one node. Later text uses "depth h" for this quantity, so the terms are inconsistent.
Second check: another model agreed
Report a problem with this finding
Wording Bucket height is defined as the bucket index "minus the index of x's least significant empty bucket", but the following claim (within a constant of log k) and the depth definition ("smallest index of a non-empty bucket") require the least significant non-empty bucket.
- p. 4 Section 3, definition of bucket height
minus the index of x’s least signifi-cant empty bucket
Only the authors can say what is right here.
Judge's note: My reworking: page 2 says low-index buckets are generally empty, so x's least significant empty bucket is typically index 0. If x is the kth-closest node to the target, its distance to the closest node is about k·2^160/n, so the bucket index is about 160 − log n + log k. Subtracting 0 gives about 160 − log n + log k, not O(log k). Subtracting the least non-empty index (about 160 − log n) gives about log k, as claimed. So the definition as printed does not support the stated claim, and "non-empty" appears to be intended. The intended result stands.
Second check: another model agreed
Report a problem with this finding
Typo Wrong word in Introduction: "finger table must store the precise node proceeding an interval in the ID space"; "proceeding" is not a positional term (probably "preceding").
- p. 1 Introduction, third paragraph
finger table must store the precise node proceeding an interval
- p. 1 Introduction, paragraph 3
must store the precise node proceeding an interval in the ID space
- p. 1 Introduction
the precise node proceeding an interval in the ID space
- p. 1
must store the precise node proceeding
Judge's note: The crop of page 1 shows "proceeding" in the typeset text. As a word for position it is wrong. The likely intended word is "preceding", but the authors should confirm whether they meant preceding or succeeding.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated word on p.2: "It is obvious that that d(x, x) = 0".
- p. 2 Section 2, paragraph on the XOR metric
It is obvious that that d(x, x) = 0
- p. 2 Figure 1 caption
The y axis shows the the fraction
- p. 3 Section 2.2
The recipient of a the RPC returns
- p. 4 Section 3
the height of a any given node
Judge's note: The page 2 crop shows "that that" in the typeset text. The other quotes in this cluster ("the the", "a the", "a any") are judged separately under C003, C005 and C006.
Second check: none (judge only)
Report a problem with this finding
Typo Duplicated article in Figure 1 caption: "The y axis shows the the fraction of nodes".
- p. 2 Figure 1 caption
The y axis shows the the fraction of nodes
- p. 2
nts minutes. The y axis shows the the fraction of nodes t
Judge's note: The crop of the Figure 1 caption on page 2 shows "the the".
Second check: code check
Report a problem with this finding
Typo Malformed abbreviation on p.2: "collected by Saroiu et. al. [4]" should be "et al.".
- p. 2 Section 2.1, last paragraph
collected by Saroiu et. al. [4]
- p. 2 Section 2.1
Saroiu et. al. [4]
Judge's note: The page 2 crop shows "et. al." in the typeset text.
Second check: none (judge only)
Report a problem with this finding
Typo Stray article in Section 2.2: "The recipient of a the RPC returns".
- p. 3 Section 2.2, FIND_NODE description
The recipient of a the RPC returns
Judge's note: The page 3 crop shows "of a the RPC".
Second check: none (judge only)
Report a problem with this finding
Typo Stray article in Section 3: "the height of a any given node will be within a constant of log n".
- p. 4 Section 3, second paragraph
the height of a any given node will be within a
- p. 4 Section 3, definitions paragraph
the height of a any given node
Judge's note: The page 4 crop shows "of a any given node".
Second check: none (judge only)
Report a problem with this finding
Typo Stray comma on p.5: "it is populated at the k nodes, closest to the key."
- p. 5 Section 3, key-value recovery paragraph
lated at the k nodes, closest to the key.
- p. 5 Section 3, key/value recovery paragraph
lated at the k nodes, closest to the key
- p. 5 Section 3
it is populated at the k nodes, closest to the key
Judge's note: The page 5 crop shows the comma before a restrictive modifier. This is a minor punctuation point.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [1] URL typeset as "http://research.microsoft.com/ãntr/pastry/": the tilde is rendered as an accent on the a, not as a literal "~antr".
- p. 5 Reference [1]
http://research.microsoft.com/˜antr/pastry/
- p. 5 References, entry [1]
http://research.microsoft.com/
Judge's note: The page 5 crop clearly shows "ãntr", with the tilde placed over the a. The text layer shows a separate tilde, but the typeset output is wrong.
Second check: none (judge only)
Report a problem with this finding
Typo Reference [1] repeats the year: "Accepted for Middleware, 2001, 2001."
- p. 5 Reference [1]
Accepted for Middleware, 2001, 2001.
- p. 5
ems. Accepted for Middleware, 2001, 2001. http://research.mi
Judge's note: The page 5 crop shows the italic venue "Accepted for Middleware, 2001" followed by the year "2001". The first 2001 is part of the venue name, so this is redundancy, not an error.
Second check: code check
Report a problem with this finding
Typo Reference [3] author list lacks a separator: "Andréa W. Richa C. Greg Plaxton, Rajmohan Rajaraman."
- p. 6 Reference [3]
Andréa W. Richa C. Greg Plaxton, Rajmo-han Rajaraman.
- p. 6 References, entry [3]
Andréa W. Richa C. Greg Plaxton, Rajmo-
- p. 5 Section 4 Discussion
Plaxton’s dis-
Judge's note: The page 6 image shows no comma or "and" between "Richa" and "C. Greg Plaxton". The other entries use the form "A, B, and C". Whether the author order is right rests on outside knowledge (the author order of the SPAA'97 paper), so I do not confirm that part. The Discussion on page 5 calls the work "Plaxton's".
Second check: none (judge only)